京都大学プログラミングコンテスト2015

Submission #535241

Source codeソースコード

#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

Task問題 H - Bit Count
User nameユーザ名 hongrock
Created time投稿日時
Language言語 C++ (GCC 4.9.2)
Status状態 AC
Score得点 300
Source lengthソースコード長 2335 Byte
File nameファイル名
Exec time実行時間 148 ms
Memory usageメモリ使用量 3480 KB

Compiler messageコンパイルメッセージ

./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);
^

Test case

Set

Set name Score得点 / Max score Cases
All 300 / 300 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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