Task: | Coins |
Sender: | Team Olari |
Submission time: | 2016-09-06 17:43:44 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.06 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.06 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.06 s | details |
#10 | ACCEPTED | 0.05 s | details |
#11 | ACCEPTED | 0.06 s | details |
#12 | ACCEPTED | 0.06 s | details |
#13 | ACCEPTED | 0.04 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.05 s | details |
#20 | ACCEPTED | 0.04 s | details |
#21 | ACCEPTED | 0.06 s | details |
#22 | ACCEPTED | 0.14 s | details |
#23 | ACCEPTED | 0.04 s | details |
#24 | ACCEPTED | 0.06 s | details |
#25 | ACCEPTED | 0.06 s | details |
#26 | ACCEPTED | 0.06 s | details |
#27 | ACCEPTED | 0.05 s | details |
#28 | ACCEPTED | 0.07 s | details |
#29 | ACCEPTED | 0.06 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.06 s | details |
#32 | ACCEPTED | 0.06 s | details |
Code
#include <iostream> #include <vector> #include <set> using namespace std; int c[101], d[101], t[10101], k[10101]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, p; cin >> n >> m >> p; set<int> s; set<int>::iterator it; s.insert(0); t[0]=k[0]=1; for(int i=0; i<n; ++i){ int a; cin >> a; for(int i=10000-a; i>=0; --i){ if(k[i]) { k[i+a]=1; } } }for(int i=0; i<m; ++i){ int a; cin >> a; for(int i=10000-a; i>=0; --i){ if(t[i]) { t[i+a]=1; s.insert(i+a); } } } int V = 10000, l=0; for(int i=p; i<=10000; ++i){ if(k[i]==0) continue; int a= i-p; it=s.upper_bound(a); --it; int b=*it; if(a-b <= V){ V=a-b; l=i; } } cout << l << " " << V; }
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 |