Submission #1990003
Source Code Expand
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> #include <iomanip> #include <cassert> #include <bitset> using namespace std; typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) #define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin()) #define _1 first #define _2 second #define pb push_back #define INF 1145141919 #define MOD 1000000007 const int MAX_S = 55*22222*2; typedef bitset<MAX_S+1> B; inline void chmin(int &x, int v) { if (x > v) x = v; } int N, M, K; B dp[56]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> K; K = min(min(N, M), K); dp[0].set(0); int sum = 0; rep(i, N) { int a; cin >> a; sum += a; for (int j=K; j>=0; j--) { if (j+1 <= K) dp[j+1] |= dp[j]; dp[j] <<= a; } } if (K == 1) dp[0] = B(); rep(i, M) { int b; cin >> b; sum += b; for (int j=1; j<=K; j++) { dp[j-1] |= dp[j]<<b; } } long long m = 0; rep(s, sum+1) if (dp[0].test(s)) m = max(m, 1LL*s*(sum-s)); cout << m << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - DDPC特別ビュッフェ |
User | funcsr |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1330 Byte |
Status | AC |
Exec Time | 674 ms |
Memory | 17664 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 | 3 ms | 1408 KB |
000_example_02.txt | AC | 3 ms | 1792 KB |
010_rand_01.txt | AC | 13 ms | 1408 KB |
010_rand_02.txt | AC | 9 ms | 1408 KB |
010_rand_03.txt | AC | 4 ms | 1408 KB |
010_rand_04.txt | AC | 4 ms | 1408 KB |
010_rand_05.txt | AC | 12 ms | 1408 KB |
020_hand_01.txt | AC | 2 ms | 1408 KB |
020_hand_02.txt | AC | 3 ms | 1408 KB |
020_hand_03.txt | AC | 8 ms | 1408 KB |
020_hand_04.txt | AC | 18 ms | 1408 KB |
020_hand_05.txt | AC | 3 ms | 1408 KB |
020_hand_06.txt | AC | 3 ms | 1408 KB |
020_hand_07.txt | AC | 3 ms | 1408 KB |
030_max_01.txt | AC | 18 ms | 1408 KB |
030_max_02.txt | AC | 17 ms | 1408 KB |
030_max_03.txt | AC | 17 ms | 1408 KB |
030_max_04.txt | AC | 17 ms | 1408 KB |
030_max_05.txt | AC | 17 ms | 1408 KB |
050_rand_01.txt | AC | 181 ms | 9088 KB |
050_rand_02.txt | AC | 10 ms | 1792 KB |
050_rand_03.txt | AC | 103 ms | 7040 KB |
060_rand_01.txt | AC | 238 ms | 9088 KB |
060_rand_02.txt | AC | 11 ms | 1792 KB |
060_rand_03.txt | AC | 119 ms | 7040 KB |
060_rand_04.txt | AC | 225 ms | 11136 KB |
060_rand_05.txt | AC | 35 ms | 2688 KB |
060_rand_06.txt | AC | 21 ms | 1792 KB |
060_rand_07.txt | AC | 68 ms | 7040 KB |
060_rand_08.txt | AC | 74 ms | 4992 KB |
060_rand_09.txt | AC | 4 ms | 1792 KB |
060_rand_10.txt | AC | 24 ms | 2688 KB |
070_rand_01.txt | AC | 280 ms | 11136 KB |
070_rand_02.txt | AC | 115 ms | 9088 KB |
070_rand_03.txt | AC | 9 ms | 2304 KB |
070_rand_04.txt | AC | 14 ms | 4992 KB |
070_rand_05.txt | AC | 151 ms | 9088 KB |
070_rand_06.txt | AC | 44 ms | 4992 KB |
070_rand_07.txt | AC | 242 ms | 11136 KB |
070_rand_08.txt | AC | 72 ms | 7040 KB |
070_rand_09.txt | AC | 74 ms | 7040 KB |
070_rand_10.txt | AC | 11 ms | 4992 KB |
080_hand_01.txt | AC | 3 ms | 1792 KB |
080_hand_02.txt | AC | 4 ms | 1792 KB |
080_hand_03.txt | AC | 5 ms | 2048 KB |
080_hand_04.txt | AC | 261 ms | 13184 KB |
080_hand_05.txt | AC | 5 ms | 2048 KB |
080_hand_06.txt | AC | 27 ms | 4992 KB |
080_hand_07.txt | AC | 508 ms | 17536 KB |
080_hand_08.txt | AC | 669 ms | 17536 KB |
080_hand_09.txt | AC | 4 ms | 1792 KB |
080_hand_10.txt | AC | 4 ms | 1792 KB |
080_hand_11.txt | AC | 4 ms | 1792 KB |
090_anti_greedy_01.txt | AC | 527 ms | 17536 KB |
090_anti_greedy_02.txt | AC | 624 ms | 17536 KB |
090_anti_greedy_03.txt | AC | 622 ms | 17536 KB |
090_anti_greedy_04.txt | AC | 650 ms | 17536 KB |
090_anti_greedy_05.txt | AC | 628 ms | 17536 KB |
090_anti_greedy_06.txt | AC | 616 ms | 17536 KB |
100_rand_01.txt | AC | 236 ms | 9088 KB |
100_rand_02.txt | AC | 11 ms | 1792 KB |
100_rand_03.txt | AC | 117 ms | 7040 KB |
100_rand_04.txt | AC | 223 ms | 11136 KB |
100_rand_05.txt | AC | 36 ms | 2688 KB |
100_rand_06.txt | AC | 21 ms | 1792 KB |
100_rand_07.txt | AC | 68 ms | 7040 KB |
100_rand_08.txt | AC | 74 ms | 4992 KB |
100_rand_09.txt | AC | 4 ms | 1792 KB |
100_rand_10.txt | AC | 25 ms | 2688 KB |
110_rand_01.txt | AC | 392 ms | 15232 KB |
110_rand_02.txt | AC | 33 ms | 4992 KB |
110_rand_03.txt | AC | 297 ms | 13184 KB |
110_rand_04.txt | AC | 263 ms | 13184 KB |
110_rand_05.txt | AC | 134 ms | 9088 KB |
110_rand_06.txt | AC | 211 ms | 9088 KB |
110_rand_07.txt | AC | 73 ms | 7040 KB |
110_rand_08.txt | AC | 145 ms | 7040 KB |
110_rand_09.txt | AC | 4 ms | 1792 KB |
110_rand_10.txt | AC | 42 ms | 4992 KB |
120_max_01.txt | AC | 655 ms | 17536 KB |
120_max_02.txt | AC | 657 ms | 17536 KB |
120_max_03.txt | AC | 647 ms | 17536 KB |
120_max_04.txt | AC | 119 ms | 4992 KB |
120_max_05.txt | AC | 142 ms | 4992 KB |
130_max_01.txt | AC | 512 ms | 17536 KB |
130_max_02.txt | AC | 514 ms | 17536 KB |
130_max_03.txt | AC | 506 ms | 17536 KB |
130_max_04.txt | AC | 519 ms | 17536 KB |
130_max_05.txt | AC | 505 ms | 17664 KB |
140_hand_01.txt | AC | 674 ms | 17536 KB |
140_hand_02.txt | AC | 10 ms | 2304 KB |
140_hand_03.txt | AC | 650 ms | 17536 KB |
140_hand_04.txt | AC | 655 ms | 17536 KB |
140_hand_05.txt | AC | 3 ms | 1792 KB |
140_hand_06.txt | AC | 4 ms | 1792 KB |
140_hand_07.txt | AC | 668 ms | 17536 KB |
140_hand_08.txt | AC | 6 ms | 2304 KB |
140_hand_09.txt | AC | 27 ms | 4992 KB |
140_hand_10.txt | AC | 512 ms | 17536 KB |
140_hand_11.txt | AC | 270 ms | 13184 KB |
140_hand_12.txt | AC | 644 ms | 17280 KB |