Task: | Coins |
Sender: | HäviöLife |
Submission time: | 2016-09-06 17:36:45 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.04 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.06 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.06 s | details |
#10 | ACCEPTED | 0.06 s | details |
#11 | ACCEPTED | 0.06 s | details |
#12 | ACCEPTED | 0.05 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.05 s | details |
#15 | ACCEPTED | 0.06 s | details |
#16 | ACCEPTED | 0.05 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.05 s | details |
#22 | ACCEPTED | 0.06 s | details |
#23 | ACCEPTED | 0.05 s | details |
#24 | ACCEPTED | 0.05 s | details |
#25 | ACCEPTED | 0.06 s | details |
#26 | ACCEPTED | 0.05 s | details |
#27 | ACCEPTED | 0.06 s | details |
#28 | ACCEPTED | 0.05 s | details |
#29 | ACCEPTED | 0.06 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.06 s | details |
#32 | ACCEPTED | 0.05 s | details |
Code
#include <iostream> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <unordered_set> #include <stdio.h> #include <string.h> #include <unordered_map> #include <fstream> #include <set> #include <map> #define MOD 1000000007 #define ll long long #define N 20000 #define float double #define str string using namespace std; int maksu[20000]; int vaihto[20000]; int S[20000]; int U[100]; int K[100]; int main(){ int n,m,p; cin>>n>>m>>p; for(int i=0; i<n; i++) cin>>U[i]; for(int i=0; i<m; i++) cin>>K[i]; for(int i=0; i<N; i++) maksu[i]=1000000; maksu[0]=0; for(int i=1; i<N; i++) for(int e=0; e<n; e++) if(i-U[e]>=0 && maksu[i-U[e]] <= e) maksu[i]=min(maksu[i],e+1); for(int i=0; i<N; i++) vaihto[i]=1000000; vaihto[0]=0; for(int i=1; i<N; i++) for(int e=0; e<m; e++) if(i-K[e]>=0 && vaihto[i-K[e]] <= e) vaihto[i]=min(vaihto[i],e+1); S[0]=0; int viimeks=0; for(int i=1; i<N; i++){ if(vaihto[i]!=1000000) viimeks=i; S[i]=viimeks; } int maara=0, menetys=1000000; for(int i=p; i<N; i++){ if(maksu[i]==1000000) continue; int menyt=(i-p)-S[i-p]; if(menyt < menetys){ menetys=menyt; maara=i; } } cout<<maara<<" "<<menetys<<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 |