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

Submission #534138

Source codeソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long ll;
static const ll INF = 1000000000000000000ll;
static ll dp[61][61][61][2];

int main(){
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--){
		ll x;
		cin >> x;
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i <= 60; ++i){
			for(int j = 0; j <= 60; ++j){
				for(int k = 0; k <= 60; ++k){
					dp[i][j][k][0] = dp[i][j][k][1] = INF;
				}
			}
		}
		dp[0][0][0][0] = 0;
		for(int i = 0; i < 60; ++i){
			for(int j = 0; j <= i; ++j){
				for(int k = 0; k <= i; ++k){
					const int d = (x >> i) & 1;
					// carry = 0, add 0
					dp[i + 1][j][k + d][0] =
						min(dp[i + 1][j][k + d][0], dp[i][j][k][0]);
					// carry = 0, add 1
					dp[i + 1][j + 1][k + (d ^ 1)][d] =
						min(dp[i + 1][j + 1][k + (d ^ 1)][d], dp[i][j][k][0] + (1ll << i));
					// carry = 1, add 0
					dp[i + 1][j][k + (d ^ 1)][d] =
						min(dp[i + 1][j][k + (d ^ 1)][d], dp[i][j][k][1]);
					// carry = 1, add 1
					dp[i + 1][j + 1][k + d][1] =
						min(dp[i + 1][j + 1][k + d][1], dp[i][j][k][1] + (1ll << i));
				}
			}
		}
		ll answer = INF;
		for(int i = 0; i <= 60; ++i){
			answer = min(answer, dp[60][i][i][0]);
		}
		cout << answer << endl;
	}
	return 0;
}

Submission

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

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 42 ms 4468 KB
10_small_00.txt AC 246 ms 4512 KB
20_medium_01.txt AC 224 ms 4388 KB
20_medium_02.txt AC 239 ms 4468 KB
20_medium_03.txt AC 225 ms 4448 KB
30_large_04.txt AC 232 ms 4388 KB
30_large_05.txt AC 249 ms 4468 KB
30_large_06.txt AC 233 ms 4516 KB
80_power_of_2.txt AC 40 ms 4380 KB