Submission #535241
Source Code Expand
#include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> using namespace std; int T; typedef long long LL; LL ans, n, dp[70][70][70]; int f[70]; int main(){ scanf("%d", &T); while(T--){ scanf("%lld", &n); memset(f, 0, sizeof(f)); int cnt = 0; for(int i=0; i<64; i++){ if(n%2==1){ f[i] = 1; cnt++; } n/=2; } memset(dp, -1, sizeof(dp)); for(int i=0; i<64; i++){ if(f[i]){ dp[i][cnt][0] = 0; break; } } ans = -1; LL cur = 1; for(int i=0; i<60; i++, cur*=2){ for(int j=0; j<=cnt; j++){ for(int k=0; k<=cnt; k++){ if(dp[i][j][k] == -1) continue; if(j == k){ if(ans == -1 || dp[i][j][k]<ans){ ans = dp[i][j][k]; continue; } } for(int l=i+1; l<60; l++){ if(f[l]){ if(dp[l][j][k]==-1 || dp[i][j][k]<dp[l][j][k]){ dp[l][j][k] = dp[i][j][k]; break; } } } for(int l=i+1; l<60; l++){ if(!f[l]){ int x = l - i; if(j>=x){ if(dp[l][j-x+1][k+1]==-1 || dp[i][j][k]+cur<dp[l][j-x+1][k+1]){ dp[l][j-x+1][k+1] = dp[i][j][k] + cur; } } break; } } } } } for(int i=0; i<60; i++){ for(int j=0; j<60; j++){ if(dp[i][j][j] != -1){ if(ans==-1 || dp[i][j][j]<ans) ans = dp[i][j][j]; } } } printf("%lld\n", ans); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Bit Count |
User | hongrock |
Language | C++ (GCC 4.9.2) |
Score | 300 |
Code Size | 2335 Byte |
Status | AC |
Exec Time | 148 ms |
Memory | 3480 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:12:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &T); ^ ./Main.cpp:14:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", &n); ^
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 300 / 300 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample.txt, 10_small_00.txt, 20_medium_01.txt, 20_medium_02.txt, 20_medium_03.txt, 30_large_04.txt, 30_large_05.txt, 30_large_06.txt, 80_power_of_2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample.txt | AC | 32 ms | 3356 KB |
10_small_00.txt | AC | 109 ms | 3480 KB |
20_medium_01.txt | AC | 112 ms | 3360 KB |
20_medium_02.txt | AC | 120 ms | 3356 KB |
20_medium_03.txt | AC | 114 ms | 3312 KB |
30_large_04.txt | AC | 141 ms | 3364 KB |
30_large_05.txt | AC | 148 ms | 3360 KB |
30_large_06.txt | AC | 140 ms | 3476 KB |
80_power_of_2.txt | AC | 32 ms | 3360 KB |