CSES - Datatähti Open 2017 - Results
Submission details
Task:Ice cream
Sender:Majakas
Submission time:2017-01-20 17:55:04 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.05 sdetails
#40.05 sdetails
#50.11 sdetails
#60.14 sdetails
#70.14 sdetails
#80.14 sdetails
#90.14 sdetails
#100.13 sdetails

Code

#include <bits/stdc++.h>
#define llong long long
#define f first
#define s second
#define mp make_pair
//#define cin fin

using namespace::std;

//ifstream fin("input.txt");

int INF = 2e6;
int LIM = 1e5 + 1;

int main()
{
    int n, x;
    cin >> n >> x;
    vector<pair<int, int> > ice(2 * n);
    for (int i = 0; i < n; i++) {
        cin >> ice[2 * i].f >> ice[2 * i].s; /// value, weight
        ice[2 * i + 1].f = ice[2 * i].f;
        ice[2 * i + 1].s = ice[2 * i].s;
    }
    n *= 2;
    vector<vector<int> > dp(n, vector<int> (LIM, INF));
    dp[0][0] = 0;
    dp[0][ice[0].s] = ice[0].f;
    int answ = 0;
    for (int i = 1; i < n; i++) {
        //cout << ice[i].f << " " << ice[i].s << "\n";
        dp[i][0] = 0;
        for (int j = 0; j < LIM; j++) {
            if (j >= ice[i].s) {
                //if (j  <= 10)
                //cout << i << " " << j << " " << dp[i - 1][j - ice[i].s] + ice[i].f << "\n";
                dp[i][j] = min(dp[i - 1][j - ice[i].s] + ice[i].f, dp[i - 1][j]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
            if (dp[i][j] <= x) {
                answ = max(answ, j);
            }
            //if (j <= 10)
            //cout << dp[i][j] << " ";
        }
        //cout << "\n";
    }
    cout << answ << "\n";

    //system("pause");
}

Test details

Test 1

Verdict: ACCEPTED

input
1 749
88 363

correct output
726

user output
726

Test 2

Verdict: ACCEPTED

input
2 902
968 550
152 228

correct output
456

user output
456

Test 3

Verdict: ACCEPTED

input
5 295
35 81
653 771
747 823
871 611
...

correct output
162

user output
162

Test 4

Verdict:

input
10 272
38 13
114 420
42 344
942 307
...

correct output
840

user output
1184

Test 5

Verdict:

input
50 468
867 254
870 736
28 739
60 609
...

correct output
2000

user output
6260

Test 6

Verdict:

input
100 739
395 712
476 916
102 614
312 533
...

correct output
1928

user output
9379

Test 7

Verdict:

input
100 781
342 898
466 888
713 516
133 389
...

correct output
1894

user output
7915

Test 8

Verdict:

input
100 297
423 506
135 31
279 441
362 969
...

correct output
1906

user output
5602

Test 9

Verdict:

input
100 875
917 956
243 815
365 575
42 846
...

correct output
1960

user output
13625

Test 10

Verdict:

input
100 651
963 307
169 423
172 150
779 998
...

correct output
1970

user output
7932