Task: | Coins |
Sender: | trukilla hissikuiluun |
Submission time: | 2016-09-06 17:43:35 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.06 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.05 s | details |
#10 | ACCEPTED | 0.05 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.06 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.05 s | details |
#15 | ACCEPTED | 0.05 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.06 s | details |
#18 | ACCEPTED | 0.05 s | details |
#19 | ACCEPTED | 0.06 s | details |
#20 | ACCEPTED | 0.06 s | details |
#21 | ACCEPTED | 0.06 s | details |
#22 | ACCEPTED | 0.03 s | details |
#23 | ACCEPTED | 0.05 s | details |
#24 | ACCEPTED | 0.05 s | details |
#25 | ACCEPTED | 0.04 s | details |
#26 | ACCEPTED | 0.05 s | details |
#27 | ACCEPTED | 0.06 s | details |
#28 | ACCEPTED | 0.08 s | details |
#29 | ACCEPTED | 0.07 s | details |
#30 | ACCEPTED | 0.06 s | details |
#31 | ACCEPTED | 0.05 s | details |
#32 | ACCEPTED | 0.06 s | details |
Code
#include <iostream> #include <set> #include <algorithm> using namespace std; int n,m,p; int c[1001]; int d[1001]; int sum1[10001]; int sum2[10001]; int main() { cin.sync_with_stdio(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]; sum1[0] = sum2[0] = 1; set<int> possib; possib.insert(0); int max1 = 0; for (int j = 0; j < n; ++j) { for (int i = max1; i >= 0; --i) { if (sum1[i] == 1) { sum1[i+c[j]] = 1; max1 = max(max1, i+c[j]); possib.insert(i+c[j]); } } } int max2 = 0; for (int j = 0; j < m; ++j) { for (int i = max2; i >=0; --i) { if (sum2[i] == 1) { sum2[i+d[j]] = 1; max2 = max(max2, i+d[j]); } } } int bestpay = -1; int bestdif = 10000000; for (int i = 0; i <= max2; ++i) { if (sum2[i]) { set<int>::iterator it = possib.lower_bound(i+p); if (it != possib.end() && (*it - i - p <= bestdif)) { bestpay = *it; bestdif = *it - i - p; } } } cout << bestpay << " " << bestdif << 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 |
---|
13 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 |
---|
3075 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 |
---|
1557 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 |
---|
5548 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 |