提出 #26044778

ソースコード 拡げる

#include<iostream>
#include<cstdio>
#define bitcnt __builtin_popcount
typedef long long ll;
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T &read(T &r) {
	r = 0; bool w = 0; char ch = getchar();
	while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
	while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
	return r = w ? -r : r;
}
const int N = 210;
const int K = 16;
const int INF = 0x7fffffff;
int n, k;
int f[(1<<K)+10];
signed main() {
	read(n); read(k);
	for(int i = 1; i <= (1<<k)-1; ++i) f[i] = INF;
	for(int i = 1; i <= n; ++i) {
		int x; read(x); --x;
		for(int j = (1<<k)-1; ~j; --j)
			if(f[j] != INF) {
				if(!(j & (1 << x)))
					f[j|(1<<x)] = Min(f[j|(1<<x)], f[j] + bitcnt(j & (~((1<<x)-1))));
				f[j] += Min(bitcnt(j), k-bitcnt(j));
			}
	}
	printf("%d\n", f[(1<<k)-1]);
	return 0;
}

提出情報

提出日時
問題 D - Pure Straight
ユーザ do_while_true
言語 C++ (GCC 9.2.1)
得点 600
コード長 966 Byte
結果 AC
実行時間 80 ms
メモリ 3940 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 3
AC × 69
セット名 テストケース
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 02_permutation_01.txt, 02_permutation_02.txt, 02_permutation_03.txt, 02_permutation_04.txt, 02_permutation_05.txt, 02_permutation_06.txt, 02_permutation_07.txt, 02_permutation_08.txt, 02_permutation_09.txt, 02_permutation_10.txt, 02_permutation_11.txt, 02_permutation_12.txt, 02_permutation_13.txt, 02_permutation_14.txt, 02_permutation_15.txt, 03_rand_01.txt, 03_rand_02.txt, 03_rand_03.txt, 03_rand_04.txt, 03_rand_05.txt, 03_rand_06.txt, 03_rand_07.txt, 03_rand_08.txt, 03_rand_09.txt, 03_rand_10.txt, 03_rand_11.txt, 03_rand_12.txt, 03_rand_13.txt, 03_rand_14.txt, 03_rand_15.txt, 03_rand_16.txt, 03_rand_17.txt, 03_rand_18.txt, 03_rand_19.txt, 03_rand_20.txt, 03_rand_21.txt, 03_rand_22.txt, 03_rand_23.txt, 03_rand_24.txt, 03_rand_25.txt, 03_rand_26.txt, 03_rand_27.txt, 03_rand_28.txt, 03_rand_29.txt, 03_rand_30.txt, 03_rand_31.txt, 03_rand_32.txt, 03_rand_33.txt, 04_large_ans_01.txt, 04_large_ans_02.txt, 04_large_ans_03.txt, 04_large_ans_04.txt, 04_large_ans_05.txt, 04_large_ans_06.txt, 04_large_ans_07.txt, 04_large_ans_08.txt, 04_large_ans_09.txt, 04_large_ans_10.txt, 04_large_ans_11.txt, 04_large_ans_12.txt, 05_partition_01.txt, 05_partition_02.txt, 05_partition_03.txt, 05_partition_04.txt, 05_partition_05.txt, 05_partition_06.txt
ケース名 結果 実行時間 メモリ
01_sample_01.txt AC 7 ms 3588 KiB
01_sample_02.txt AC 2 ms 3604 KiB
01_sample_03.txt AC 2 ms 3652 KiB
02_permutation_01.txt AC 3 ms 3640 KiB
02_permutation_02.txt AC 2 ms 3656 KiB
02_permutation_03.txt AC 2 ms 3560 KiB
02_permutation_04.txt AC 3 ms 3504 KiB
02_permutation_05.txt AC 3 ms 3688 KiB
02_permutation_06.txt AC 2 ms 3592 KiB
02_permutation_07.txt AC 2 ms 3576 KiB
02_permutation_08.txt AC 3 ms 3604 KiB
02_permutation_09.txt AC 2 ms 3648 KiB
02_permutation_10.txt AC 2 ms 3644 KiB
02_permutation_11.txt AC 2 ms 3524 KiB
02_permutation_12.txt AC 2 ms 3724 KiB
02_permutation_13.txt AC 4 ms 3752 KiB
02_permutation_14.txt AC 4 ms 3784 KiB
02_permutation_15.txt AC 6 ms 3760 KiB
03_rand_01.txt AC 2 ms 3532 KiB
03_rand_02.txt AC 3 ms 3552 KiB
03_rand_03.txt AC 2 ms 3548 KiB
03_rand_04.txt AC 2 ms 3564 KiB
03_rand_05.txt AC 3 ms 3580 KiB
03_rand_06.txt AC 2 ms 3604 KiB
03_rand_07.txt AC 5 ms 3560 KiB
03_rand_08.txt AC 4 ms 3600 KiB
03_rand_09.txt AC 6 ms 3592 KiB
03_rand_10.txt AC 8 ms 3648 KiB
03_rand_11.txt AC 14 ms 3604 KiB
03_rand_12.txt AC 22 ms 3596 KiB
03_rand_13.txt AC 22 ms 3612 KiB
03_rand_14.txt AC 40 ms 3712 KiB
03_rand_15.txt AC 44 ms 3820 KiB
03_rand_16.txt AC 44 ms 3728 KiB
03_rand_17.txt AC 46 ms 3788 KiB
03_rand_18.txt AC 41 ms 3716 KiB
03_rand_19.txt AC 46 ms 3652 KiB
03_rand_20.txt AC 43 ms 3708 KiB
03_rand_21.txt AC 45 ms 3664 KiB
03_rand_22.txt AC 46 ms 3724 KiB
03_rand_23.txt AC 44 ms 3788 KiB
03_rand_24.txt AC 71 ms 3760 KiB
03_rand_25.txt AC 76 ms 3780 KiB
03_rand_26.txt AC 78 ms 3780 KiB
03_rand_27.txt AC 68 ms 3840 KiB
03_rand_28.txt AC 80 ms 3852 KiB
03_rand_29.txt AC 72 ms 3892 KiB
03_rand_30.txt AC 78 ms 3812 KiB
03_rand_31.txt AC 72 ms 3832 KiB
03_rand_32.txt AC 73 ms 3800 KiB
03_rand_33.txt AC 75 ms 3776 KiB
04_large_ans_01.txt AC 26 ms 3812 KiB
04_large_ans_02.txt AC 23 ms 3656 KiB
04_large_ans_03.txt AC 30 ms 3840 KiB
04_large_ans_04.txt AC 16 ms 3724 KiB
04_large_ans_05.txt AC 34 ms 3828 KiB
04_large_ans_06.txt AC 16 ms 3640 KiB
04_large_ans_07.txt AC 32 ms 3776 KiB
04_large_ans_08.txt AC 19 ms 3788 KiB
04_large_ans_09.txt AC 29 ms 3816 KiB
04_large_ans_10.txt AC 18 ms 3816 KiB
04_large_ans_11.txt AC 23 ms 3840 KiB
04_large_ans_12.txt AC 17 ms 3692 KiB
05_partition_01.txt AC 36 ms 3940 KiB
05_partition_02.txt AC 18 ms 3712 KiB
05_partition_03.txt AC 37 ms 3844 KiB
05_partition_04.txt AC 20 ms 3640 KiB
05_partition_05.txt AC 35 ms 3828 KiB
05_partition_06.txt AC 27 ms 3676 KiB