Task: | Coins |
Sender: | Pietari Kaskela |
Submission time: | 2016-09-06 18:05:56 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.10 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.06 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.05 s | details |
#10 | ACCEPTED | 0.06 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.05 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.09 s | details |
#15 | ACCEPTED | 0.05 s | details |
#16 | ACCEPTED | 0.06 s | details |
#17 | ACCEPTED | 0.05 s | details |
#18 | ACCEPTED | 0.05 s | details |
#19 | ACCEPTED | 0.05 s | details |
#20 | ACCEPTED | 0.05 s | details |
#21 | ACCEPTED | 0.06 s | details |
#22 | ACCEPTED | 0.05 s | details |
#23 | ACCEPTED | 0.05 s | details |
#24 | ACCEPTED | 0.05 s | details |
#25 | ACCEPTED | 0.05 s | details |
#26 | ACCEPTED | 0.07 s | details |
#27 | ACCEPTED | 0.07 s | details |
#28 | ACCEPTED | 0.06 s | details |
#29 | ACCEPTED | 0.07 s | details |
#30 | ACCEPTED | 0.06 s | details |
#31 | ACCEPTED | 0.06 s | details |
#32 | ACCEPTED | 0.06 s | details |
Code
#include <bits/stdc++.h> #define i64 long long #define u64 unsigned long long #define i32 int #define u32 unsigned int #define pii pair<int, int> #define pll pair<long long, long long> #define ld long double #define defmod 1000000007 #define mati64(a,b) vector<vector<i64>>(a, vector<i64>(b, 0)); using namespace std; i64 n, m, p; i64 c[101], d[101]; int main(){ cin.sync_with_stdio(0); cin.tie(0); cin >> n >> m >> p; for(int i = 0; i < n; ++i) cin >> c[i]; for(int i = 0; i < m; ++i) cin >> d[i]; int up[10100] = {0}, dp[10100] = {0}; up[0] = 1; for(int i = 0; i < n; ++i){ for(int j = 10000; j >= 0; j--){ if(c[i]+j > 10000 || up[j] == 0) continue; up[c[i]+j] = 1; } } dp[0] = 1; for(int i = 0; i < m; ++i){ for(int j = 2000; j >= 0; j--){ if(d[i]+j > 2000 || dp[j] == 0) continue; dp[d[i]+j] = 1; } } int a1 = 90000, a2 = 90000; for(int i = p; i <= 10000; ++i){ if(!up[i]) continue; int l2 = i-p; if(l2 < a2){ a1 = i; a2 = l2; } for(int j = 0; i-j >= p; ++j){ if(dp[j] == 0) continue; int lose = i-j-p; if(lose < a2){ a1 = i; a2 = lose; } } } cout << a1 << " " << a2 << endl; return 0; }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
2 1 3 5 2 3 |
correct output |
---|
7 1 |
user output |
---|
7 1 |
Test 2
Verdict: ACCEPTED
input |
---|
3 3 10 6 7 6 1 1 1 |
correct output |
---|
13 0 |
user output |
---|
12 0 |
Test 3
Verdict: ACCEPTED
input |
---|
15 7 1000 93 87 95 76 95 40 57 80 90 86 ... |
correct output |
---|
1004 4 |
user output |
---|
1004 4 |
Test 4
Verdict: ACCEPTED
input |
---|
14 0 1000 84 77 81 91 78 29 96 47 87 69 ... |
correct output |
---|
1008 8 |
user output |
---|
1008 8 |
Test 5
Verdict: ACCEPTED
input |
---|
13 51 1000 96 39 46 94 56 92 59 97 85 55 ... |
correct output |
---|
1010 10 |
user output |
---|
1010 10 |
Test 6
Verdict: ACCEPTED
input |
---|
13 27 1000 94 91 97 90 71 75 95 80 72 71 ... |
correct output |
---|
1001 1 |
user output |
---|
1001 1 |
Test 7
Verdict: ACCEPTED
input |
---|
13 2 1000 69 71 87 66 78 97 95 70 77 92 ... |
correct output |
---|
1002 1 |
user output |
---|
1002 1 |
Test 8
Verdict: ACCEPTED
input |
---|
15 8 1000 62 90 65 35 64 59 80 91 87 80 ... |
correct output |
---|
1002 2 |
user output |
---|
1002 2 |
Test 9
Verdict: ACCEPTED
input |
---|
17 95 1000 45 44 37 60 45 79 83 64 23 77 ... |
correct output |
---|
1009 2 |
user output |
---|
1009 2 |
Test 10
Verdict: ACCEPTED
input |
---|
27 73 1000 69 46 79 15 73 56 39 52 33 48 ... |
correct output |
---|
1001 1 |
user output |
---|
1001 1 |
Test 11
Verdict: ACCEPTED
input |
---|
5 43 336 71 44 84 81 99 46 78 55 48 81 62 97 98 80 96 ... |
correct output |
---|
379 1 |
user output |
---|
379 1 |
Test 12
Verdict: ACCEPTED
input |
---|
10 75 699 70 55 76 85 79 86 32 83 76 62 37 85 79 66 44 30 57 32 70 71 ... |
correct output |
---|
704 5 |
user output |
---|
704 5 |
Test 13
Verdict: ACCEPTED
input |
---|
13 1 2 86 58 71 98 73 94 50 76 50 44 ... |
correct output |
---|
44 33 |
user output |
---|
44 33 |
Test 14
Verdict: ACCEPTED
input |
---|
6 31 202 20 27 66 30 38 73 73 37 89 81 97 93 97 87 28 65 ... |
correct output |
---|
204 2 |
user output |
---|
204 2 |
Test 15
Verdict: ACCEPTED
input |
---|
12 9 884 68 96 99 50 60 59 100 94 88 70... |
correct output |
---|
942 2 |
user output |
---|
942 2 |
Test 16
Verdict: ACCEPTED
input |
---|
5 12 138 25 34 91 24 4 68 78 99 58 32 72 89 76 88 52 ... |
correct output |
---|
140 2 |
user output |
---|
140 2 |
Test 17
Verdict: ACCEPTED
input |
---|
11 1 199 91 94 75 89 89 61 88 84 96 80 ... |
correct output |
---|
297 3 |
user output |
---|
297 3 |
Test 18
Verdict: ACCEPTED
input |
---|
5 36 389 86 80 100 89 59 100 60 98 32 100 67 82 100 85 ... |
correct output |
---|
414 3 |
user output |
---|
414 3 |
Test 19
Verdict: ACCEPTED
input |
---|
10 69 210 11 15 45 51 3 14 12 8 42 22 99 56 46 79 43 68 47 71 68 77 ... |
correct output |
---|
211 1 |
user output |
---|
211 1 |
Test 20
Verdict: ACCEPTED
input |
---|
6 15 334 95 67 33 39 55 50 68 57 76 76 75 91 42 75 100 48... |
correct output |
---|
339 5 |
user output |
---|
339 5 |
Test 21
Verdict: ACCEPTED
input |
---|
5 28 360 86 89 82 62 97 57 94 27 57 75 87 63 88 75 43 ... |
correct output |
---|
416 2 |
user output |
---|
416 2 |
Test 22
Verdict: ACCEPTED
input |
---|
8 97 588 87 77 81 56 86 99 99 93 59 70 75 98 91 70 95 99 64 69 ... |
correct output |
---|
678 1 |
user output |
---|
678 1 |
Test 23
Verdict: ACCEPTED
input |
---|
8 33 526 65 43 98 29 77 73 58 97 52 25 25 19 22 5 34 42 19 75 5... |
correct output |
---|
540 2 |
user output |
---|
540 2 |
Test 24
Verdict: ACCEPTED
input |
---|
10 22 743 86 85 96 84 92 98 99 83 57 40 67 29 81 93 96 65 68 90 67 50 ... |
correct output |
---|
820 4 |
user output |
---|
820 4 |
Test 25
Verdict: ACCEPTED
input |
---|
4 12 249 94 95 93 98 91 72 92 61 56 92 63 95 45 83 ... |
correct output |
---|
380 2 |
user output |
---|
380 2 |
Test 26
Verdict: ACCEPTED
input |
---|
100 100 1000 49 20 56 23 51 37 51 42 55 49 ... |
correct output |
---|
1000 0 |
user output |
---|
1000 0 |
Test 27
Verdict: ACCEPTED
input |
---|
100 0 1000 94 89 71 71 96 100 85 83 77 83... |
correct output |
---|
1000 0 |
user output |
---|
1000 0 |
Test 28
Verdict: ACCEPTED
input |
---|
20 100 1000 88 99 97 98 78 88 90 60 71 90 ... |
correct output |
---|
1000 0 |
user output |
---|
1000 0 |
Test 29
Verdict: ACCEPTED
input |
---|
100 100 1 99 90 80 98 96 77 59 86 51 69 ... |
correct output |
---|
30 0 |
user output |
---|
30 0 |
Test 30
Verdict: ACCEPTED
input |
---|
100 0 1 100 98 100 100 100 99 99 100 9... |
correct output |
---|
95 94 |
user output |
---|
95 94 |
Test 31
Verdict: ACCEPTED
input |
---|
1 100 1 33 99 95 100 100 100 97 99 100 99... |
correct output |
---|
33 32 |
user output |
---|
33 32 |
Test 32
Verdict: ACCEPTED
input |
---|
80 14 999 100 100 100 100 100 100 100 10... |
correct output |
---|
2300 0 |
user output |
---|
2300 0 |