Submission #1987721
Source Code Expand
#include <iostream> #include <algorithm> using namespace std; int N, M, K, a, s; long long ret, dp[2444444]; int main() { cin >> N >> M >> K; dp[0] = 1; for (int i = 0; i < N; i++) { cin >> a; s += a; for (int j = s; j >= a; j--) dp[j] |= dp[j - a] << 1; } for (int i = 0; i <= s; i++) { for (int j = 0; j <= N; j++) { if (j < N - K || (K == 1 && j != N - 1) || (K >= 2 && j == N - K && j % 2 != (N - K % 2) % 2)) { dp[i] &= ~(1LL << j); } } } for (int i = 0; i < M; i++) { cin >> a; s += a; for (int j = s; j >= a; j--) { dp[j] |= dp[j - a] << 1; if ((dp[j] >> (N + 1)) & 1) dp[j] -= 1LL << (N + 1); } } for (int i = 0; i <= s; i++) { if ((dp[i] >> N) & 1) ret = max(ret, 1LL * i * (s - i)); } cout << ret << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - DDPC特別ビュッフェ |
User | square1001 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 801 Byte |
Status | AC |
Exec Time | 302 ms |
Memory | 19328 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 10 / 10 | 20 / 20 | 70 / 70 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 000_example_01.txt, 000_example_02.txt |
Subtask1 | 000_example_01.in, 010_rand_01.txt, 010_rand_02.txt, 010_rand_03.txt, 010_rand_04.txt, 010_rand_05.txt, 020_hand_01.txt, 020_hand_02.txt, 020_hand_03.txt, 020_hand_04.txt, 020_hand_05.txt, 020_hand_06.txt, 020_hand_07.txt, 030_max_01.txt, 030_max_02.txt, 030_max_03.txt, 030_max_04.txt, 030_max_05.txt |
Subtask2 | 000_example_01.txt, 000_example_02.txt, 020_hand_01.txt, 020_hand_03.txt, 020_hand_07.txt, 050_rand_01.txt, 050_rand_02.txt, 050_rand_03.txt, 060_rand_01.txt, 060_rand_02.txt, 060_rand_03.txt, 060_rand_04.txt, 060_rand_05.txt, 060_rand_06.txt, 060_rand_07.txt, 060_rand_08.txt, 060_rand_09.txt, 060_rand_10.txt, 070_rand_01.txt, 070_rand_02.txt, 070_rand_03.txt, 070_rand_04.txt, 070_rand_05.txt, 070_rand_06.txt, 070_rand_07.txt, 070_rand_08.txt, 070_rand_09.txt, 070_rand_10.txt, 080_hand_01.txt, 080_hand_02.txt, 080_hand_03.txt, 080_hand_04.txt, 080_hand_05.txt, 080_hand_06.txt, 080_hand_07.txt, 080_hand_08.txt, 080_hand_09.txt, 080_hand_10.txt, 080_hand_11.txt, 090_anti_greedy_01.txt, 090_anti_greedy_02.txt, 090_anti_greedy_03.txt, 090_anti_greedy_04.txt, 090_anti_greedy_05.txt, 090_anti_greedy_06.txt |
All | 000_example_01.txt, 000_example_02.txt, 010_rand_01.txt, 010_rand_02.txt, 010_rand_03.txt, 010_rand_04.txt, 010_rand_05.txt, 020_hand_01.txt, 020_hand_02.txt, 020_hand_03.txt, 020_hand_04.txt, 020_hand_05.txt, 020_hand_06.txt, 020_hand_07.txt, 030_max_01.txt, 030_max_02.txt, 030_max_03.txt, 030_max_04.txt, 030_max_05.txt, 050_rand_01.txt, 050_rand_02.txt, 050_rand_03.txt, 060_rand_01.txt, 060_rand_02.txt, 060_rand_03.txt, 060_rand_04.txt, 060_rand_05.txt, 060_rand_06.txt, 060_rand_07.txt, 060_rand_08.txt, 060_rand_09.txt, 060_rand_10.txt, 070_rand_01.txt, 070_rand_02.txt, 070_rand_03.txt, 070_rand_04.txt, 070_rand_05.txt, 070_rand_06.txt, 070_rand_07.txt, 070_rand_08.txt, 070_rand_09.txt, 070_rand_10.txt, 080_hand_01.txt, 080_hand_02.txt, 080_hand_03.txt, 080_hand_04.txt, 080_hand_05.txt, 080_hand_06.txt, 080_hand_07.txt, 080_hand_08.txt, 080_hand_09.txt, 080_hand_10.txt, 080_hand_11.txt, 090_anti_greedy_01.txt, 090_anti_greedy_02.txt, 090_anti_greedy_03.txt, 090_anti_greedy_04.txt, 090_anti_greedy_05.txt, 090_anti_greedy_06.txt, 100_rand_01.txt, 100_rand_02.txt, 100_rand_03.txt, 100_rand_04.txt, 100_rand_05.txt, 100_rand_06.txt, 100_rand_07.txt, 100_rand_08.txt, 100_rand_09.txt, 100_rand_10.txt, 110_rand_01.txt, 110_rand_02.txt, 110_rand_03.txt, 110_rand_04.txt, 110_rand_05.txt, 110_rand_06.txt, 110_rand_07.txt, 110_rand_08.txt, 110_rand_09.txt, 110_rand_10.txt, 120_max_01.txt, 120_max_02.txt, 120_max_03.txt, 120_max_04.txt, 120_max_05.txt, 130_max_01.txt, 130_max_02.txt, 130_max_03.txt, 130_max_04.txt, 130_max_05.txt, 140_hand_01.txt, 140_hand_02.txt, 140_hand_03.txt, 140_hand_04.txt, 140_hand_05.txt, 140_hand_06.txt, 140_hand_07.txt, 140_hand_08.txt, 140_hand_09.txt, 140_hand_10.txt, 140_hand_11.txt, 140_hand_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
000_example_01.txt | AC | 1 ms | 256 KB |
000_example_02.txt | AC | 1 ms | 256 KB |
010_rand_01.txt | AC | 70 ms | 8448 KB |
010_rand_02.txt | AC | 40 ms | 6400 KB |
010_rand_03.txt | AC | 4 ms | 1792 KB |
010_rand_04.txt | AC | 4 ms | 1536 KB |
010_rand_05.txt | AC | 102 ms | 8448 KB |
020_hand_01.txt | AC | 1 ms | 256 KB |
020_hand_02.txt | AC | 1 ms | 256 KB |
020_hand_03.txt | AC | 1 ms | 256 KB |
020_hand_04.txt | AC | 302 ms | 19328 KB |
020_hand_05.txt | AC | 1 ms | 256 KB |
020_hand_06.txt | AC | 1 ms | 256 KB |
020_hand_07.txt | AC | 1 ms | 256 KB |
030_max_01.txt | AC | 162 ms | 10496 KB |
030_max_02.txt | AC | 156 ms | 10496 KB |
030_max_03.txt | AC | 164 ms | 10496 KB |
030_max_04.txt | AC | 154 ms | 10496 KB |
030_max_05.txt | AC | 154 ms | 10496 KB |
050_rand_01.txt | AC | 1 ms | 256 KB |
050_rand_02.txt | AC | 1 ms | 256 KB |
050_rand_03.txt | AC | 1 ms | 256 KB |
060_rand_01.txt | AC | 1 ms | 256 KB |
060_rand_02.txt | AC | 1 ms | 256 KB |
060_rand_03.txt | AC | 2 ms | 256 KB |
060_rand_04.txt | AC | 1 ms | 256 KB |
060_rand_05.txt | AC | 1 ms | 256 KB |
060_rand_06.txt | AC | 1 ms | 256 KB |
060_rand_07.txt | AC | 1 ms | 256 KB |
060_rand_08.txt | AC | 1 ms | 256 KB |
060_rand_09.txt | AC | 1 ms | 256 KB |
060_rand_10.txt | AC | 1 ms | 256 KB |
070_rand_01.txt | AC | 1 ms | 256 KB |
070_rand_02.txt | AC | 1 ms | 256 KB |
070_rand_03.txt | AC | 1 ms | 256 KB |
070_rand_04.txt | AC | 1 ms | 256 KB |
070_rand_05.txt | AC | 1 ms | 256 KB |
070_rand_06.txt | AC | 1 ms | 256 KB |
070_rand_07.txt | AC | 1 ms | 256 KB |
070_rand_08.txt | AC | 1 ms | 256 KB |
070_rand_09.txt | AC | 1 ms | 256 KB |
070_rand_10.txt | AC | 1 ms | 256 KB |
080_hand_01.txt | AC | 1 ms | 256 KB |
080_hand_02.txt | AC | 1 ms | 256 KB |
080_hand_03.txt | AC | 1 ms | 256 KB |
080_hand_04.txt | AC | 1 ms | 256 KB |
080_hand_05.txt | AC | 1 ms | 256 KB |
080_hand_06.txt | AC | 1 ms | 256 KB |
080_hand_07.txt | AC | 1 ms | 256 KB |
080_hand_08.txt | AC | 2 ms | 256 KB |
080_hand_09.txt | AC | 1 ms | 256 KB |
080_hand_10.txt | AC | 1 ms | 256 KB |
080_hand_11.txt | AC | 1 ms | 256 KB |
090_anti_greedy_01.txt | AC | 1 ms | 256 KB |
090_anti_greedy_02.txt | AC | 2 ms | 256 KB |
090_anti_greedy_03.txt | AC | 2 ms | 256 KB |
090_anti_greedy_04.txt | AC | 2 ms | 256 KB |
090_anti_greedy_05.txt | AC | 2 ms | 256 KB |
090_anti_greedy_06.txt | AC | 2 ms | 256 KB |
100_rand_01.txt | AC | 27 ms | 4352 KB |
100_rand_02.txt | AC | 11 ms | 1408 KB |
100_rand_03.txt | AC | 38 ms | 4352 KB |
100_rand_04.txt | AC | 23 ms | 4352 KB |
100_rand_05.txt | AC | 11 ms | 1408 KB |
100_rand_06.txt | AC | 25 ms | 4352 KB |
100_rand_07.txt | AC | 7 ms | 1280 KB |
100_rand_08.txt | AC | 12 ms | 1792 KB |
100_rand_09.txt | AC | 2 ms | 640 KB |
100_rand_10.txt | AC | 9 ms | 1664 KB |
110_rand_01.txt | AC | 29 ms | 4352 KB |
110_rand_02.txt | AC | 14 ms | 1408 KB |
110_rand_03.txt | AC | 38 ms | 4352 KB |
110_rand_04.txt | AC | 23 ms | 4352 KB |
110_rand_05.txt | AC | 11 ms | 1408 KB |
110_rand_06.txt | AC | 23 ms | 4352 KB |
110_rand_07.txt | AC | 7 ms | 1280 KB |
110_rand_08.txt | AC | 13 ms | 1792 KB |
110_rand_09.txt | AC | 2 ms | 640 KB |
110_rand_10.txt | AC | 10 ms | 1664 KB |
120_max_01.txt | AC | 48 ms | 4352 KB |
120_max_02.txt | AC | 43 ms | 4352 KB |
120_max_03.txt | AC | 48 ms | 4352 KB |
120_max_04.txt | AC | 53 ms | 4352 KB |
120_max_05.txt | AC | 38 ms | 4352 KB |
130_max_01.txt | AC | 81 ms | 4352 KB |
130_max_02.txt | AC | 71 ms | 4352 KB |
130_max_03.txt | AC | 80 ms | 4352 KB |
130_max_04.txt | AC | 88 ms | 4352 KB |
130_max_05.txt | AC | 68 ms | 4352 KB |
140_hand_01.txt | AC | 300 ms | 19200 KB |
140_hand_02.txt | AC | 3 ms | 512 KB |
140_hand_03.txt | AC | 218 ms | 16640 KB |
140_hand_04.txt | AC | 235 ms | 18688 KB |
140_hand_05.txt | AC | 1 ms | 384 KB |
140_hand_06.txt | AC | 1 ms | 256 KB |
140_hand_07.txt | AC | 300 ms | 19200 KB |
140_hand_08.txt | AC | 2 ms | 768 KB |
140_hand_09.txt | AC | 10 ms | 4352 KB |
140_hand_10.txt | AC | 48 ms | 10368 KB |
140_hand_11.txt | AC | 7 ms | 640 KB |
140_hand_12.txt | AC | 10 ms | 640 KB |