CSES - KILO 2016 1/5

Submission details
Task:	Coins
Sender:	OOliOO_slayer
Submission time:	2016-09-06 18:53:28 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.05 s	details
#5	ACCEPTED	0.05 s	details
#6	ACCEPTED	0.06 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.05 s	details
#12	ACCEPTED	0.05 s	details
#13	ACCEPTED	0.06 s	details
#14	ACCEPTED	0.06 s	details
#15	ACCEPTED	0.03 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.05 s	details
#21	ACCEPTED	0.05 s	details
#22	ACCEPTED	0.06 s	details
#23	ACCEPTED	0.06 s	details
#24	ACCEPTED	0.06 s	details
#25	ACCEPTED	0.04 s	details
#26	ACCEPTED	0.06 s	details
#27	ACCEPTED	0.07 s	details
#28	ACCEPTED	0.06 s	details
#29	ACCEPTED	0.07 s	details
#30	ACCEPTED	0.07 s	details
#31	ACCEPTED	0.05 s	details
#32	ACCEPTED	0.05 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:37:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < coins_u.size(); i++){
                                   ^
input/code.cpp:45:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < coins_c.size(); i++){
                                   ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <set>

using namespace std;

typedef long long LL;

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n_uolevi, n_cashier, target;
  cin >> n_uolevi >> n_cashier >> target;
  vector<int> coins_u, coins_c;
  coins_u.push_back(0);
  coins_c.push_back(0);
  for(int i = 0; i < n_uolevi; i++){
    int x; cin >> x;
    coins_u.push_back(x);
  }
  
  for(int i = 0; i < n_cashier; i++){
    int x; cin >> x;
    coins_c.push_back(x);
  }
  
  vector<vector<bool> > dpu(101, vector<bool>(100*100 + 1)); // using first, sum
  vector<vector<bool> > dpc(101, vector<bool>(100*100 + 1)); // using first, sum
  dpu[0][0] = true; dpc[0][0] = true;
  
  for(int i = 1; i < coins_u.size(); i++){
    for(int s = 0; s <= 100*100; s++){
      //cout << i << " " << s << endl;
      dpu[i][s] = dpu[i][s] || dpu[i-1][s];
      if(s-coins_u[i] >= 0) dpu[i][s] = dpu[i][s] || dpu[i-1][s-coins_u[i]];
    }
  }

  for(int i = 1; i < coins_c.size(); i++){
    for(int s = 0; s <= 100*100; s++){
      dpc[i][s] = dpc[i][s] || dpc[i-1][s];
      if(s-coins_c[i] >= 0) dpc[i][s] = dpc[i][s] || dpc[i-1][s-coins_c[i]];
    }
  }
  
  //for(int i = 0; i < 15; i++) cout << (int)dpu[n_uolevi][i] << " "; cout << endl;
  //for(int i = 0; i < 15; i++) cout << (int)dpc[n_cashier][i] << " "; cout << endl;
  
  int best = 1e9;
  int best_amount = 0;
  for(int i = target; i <= 100*100; i++){
    if(dpu[n_uolevi][i] == false) continue;
    int change = i - target;
    for(int j = change; j >= 0; j--){
      if(dpc[n_cashier][j]){
	if(change - j < best){
	  best = change - j;
	  best_amount = i;
	}
      }
    }
  }
  
  cout << best_amount << " " << best << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 3 5 2 3` view save

correct output
`7 1` view save

user output
`7 1` view save

Test 2

Verdict: ACCEPTED

input
`3 3 10 6 7 6 1 1 1` view save

correct output
`13 0` view save

user output
`12 0` view save

Test 3

Verdict: ACCEPTED

input
`15 7 1000 93 87 95 76 95 40 57 80 90 86 ...` view save

correct output
`1004 4` view save

user output
`1004 4` view save

Test 4

Verdict: ACCEPTED

input
`14 0 1000 84 77 81 91 78 29 96 47 87 69 ...` view save

correct output
`1008 8` view save

user output
`1008 8` view save

Test 5

Verdict: ACCEPTED

input
`13 51 1000 96 39 46 94 56 92 59 97 85 55 ...` view save

correct output
`1010 10` view save

user output
`1010 10` view save

Test 6

Verdict: ACCEPTED

input
`13 27 1000 94 91 97 90 71 75 95 80 72 71 ...` view save

correct output
`1001 1` view save

user output
`1001 1` view save

Test 7

Verdict: ACCEPTED

input
`13 2 1000 69 71 87 66 78 97 95 70 77 92 ...` view save

correct output
`1002 1` view save

user output
`1002 1` view save

Test 8

Verdict: ACCEPTED

input
`15 8 1000 62 90 65 35 64 59 80 91 87 80 ...` view save

correct output
`1002 2` view save

user output
`1002 2` view save

Test 9

Verdict: ACCEPTED

input
`17 95 1000 45 44 37 60 45 79 83 64 23 77 ...` view save

correct output
`1009 2` view save

user output
`1009 2` view save

Test 10

Verdict: ACCEPTED

input
`27 73 1000 69 46 79 15 73 56 39 52 33 48 ...` view save

correct output
`1001 1` view save

user output
`1001 1` view save

Test 11

Verdict: ACCEPTED

input
`5 43 336 71 44 84 81 99 46 78 55 48 81 62 97 98 80 96 ...` view save

correct output
`379 1` view save

user output
`379 1` view save

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 ...` view save

correct output
`704 5` view save

user output
`704 5` view save

Test 13

Verdict: ACCEPTED

input
`13 1 2 86 58 71 98 73 94 50 76 50 44 ...` view save

correct output
`44 33` view save

user output
`44 33` view save

Test 14

Verdict: ACCEPTED

input
`6 31 202 20 27 66 30 38 73 73 37 89 81 97 93 97 87 28 65 ...` view save

correct output
`204 2` view save

user output
`204 2` view save

Test 15

Verdict: ACCEPTED

input
`12 9 884 68 96 99 50 60 59 100 94 88 70...` view save

correct output
`942 2` view save

user output
`942 2` view save

Test 16

Verdict: ACCEPTED

input
`5 12 138 25 34 91 24 4 68 78 99 58 32 72 89 76 88 52 ...` view save

correct output
`140 2` view save

user output
`140 2` view save

Test 17

Verdict: ACCEPTED

input
`11 1 199 91 94 75 89 89 61 88 84 96 80 ...` view save

correct output
`297 3` view save

user output
`297 3` view save

Test 18

Verdict: ACCEPTED

input
`5 36 389 86 80 100 89 59 100 60 98 32 100 67 82 100 85 ...` view save

correct output
`414 3` view save

user output
`414 3` view save

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 ...` view save

correct output
`211 1` view save

user output
`211 1` view save

Test 20

Verdict: ACCEPTED

input
`6 15 334 95 67 33 39 55 50 68 57 76 76 75 91 42 75 100 48...` view save

correct output
`339 5` view save

user output
`339 5` view save

Test 21

Verdict: ACCEPTED

input
`5 28 360 86 89 82 62 97 57 94 27 57 75 87 63 88 75 43 ...` view save

correct output
`416 2` view save

user output
`416 2` view save

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 ...` view save

correct output
`678 1` view save

user output
`678 1` view save

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...` view save

correct output
`540 2` view save

user output
`540 2` view save

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 ...` view save

correct output
`820 4` view save

user output
`820 4` view save

Test 25

Verdict: ACCEPTED

input
`4 12 249 94 95 93 98 91 72 92 61 56 92 63 95 45 83 ...` view save

correct output
`380 2` view save

user output
`380 2` view save

Test 26

Verdict: ACCEPTED

input
`100 100 1000 49 20 56 23 51 37 51 42 55 49 ...` view save

correct output
`1000 0` view save

user output
`1000 0` view save

Test 27

Verdict: ACCEPTED

input
`100 0 1000 94 89 71 71 96 100 85 83 77 83...` view save

correct output
`1000 0` view save

user output
`1000 0` view save

Test 28

Verdict: ACCEPTED

input
`20 100 1000 88 99 97 98 78 88 90 60 71 90 ...` view save

correct output
`1000 0` view save

user output
`1000 0` view save

Test 29

Verdict: ACCEPTED

input
`100 100 1 99 90 80 98 96 77 59 86 51 69 ...` view save

correct output
`30 0` view save

user output
`30 0` view save

Test 30

Verdict: ACCEPTED

input
`100 0 1 100 98 100 100 100 99 99 100 9...` view save

correct output
`95 94` view save

user output
`95 94` view save

Test 31

Verdict: ACCEPTED

input
`1 100 1 33 99 95 100 100 100 97 99 100 99...` view save

correct output
`33 32` view save

user output
`33 32` view save

Test 32

Verdict: ACCEPTED

input
`80 14 999 100 100 100 100 100 100 100 10...` view save

correct output
`2300 0` view save

user output
`2300 0` view save

KILO 2016 1/5

Coins

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Tasks

Submissions (OOliOO_slayer)