Submission #3944183


Source Code Expand

Copy
#include <bits/stdc++.h>

#define ll long long
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll mod=1000000007;

using namespace std;

int n,d[100100];
int w,wgh[110],val[110];

int main(){
    for (int i=0;i<100100;i++)d[i]=2e9;
    cin>>n>>w;
    for (int i=1;i<=n;i++){
        cin>>wgh[i]>>val[i];
    }
    for (int i=1;i<=n;i++){
        vector<pair<int,int>>v;
        for (int j=1;j<=1e5;j++){
            if (val[i]==j){
                if (wgh[i]>w)continue;

                v.push_back({j,wgh[i]});
            }
            if (val[i]>=j)continue;
            if (d[j-val[i]]==2e9)continue;
            if (d[j-val[i]]+wgh[i]>w)continue;

            v.push_back({j,d[j-val[i]]+wgh[i]});
        }
        for (auto j:v){
            d[j.first]=min(d[j.first],j.second);
        }
    }
    for (int i=1e5;i>=1;i--){
        if (d[i]<=w){
            return cout<<i,0;
        }
    }
    cout<<0;
	return 0;
}

Submission Info

Submission Time
Task E - Knapsack 2
User Brankonymous
Language C++14 (GCC 5.4.1)
Score 100
Code Size 991 Byte
Status
Exec Time 58 ms
Memory 1596 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17
Case Name Status Exec Time Memory
0_00 2 ms 640 KB
0_01 2 ms 640 KB
0_02 3 ms 640 KB
1_00 2 ms 640 KB
1_01 25 ms 640 KB
1_02 26 ms 640 KB
1_03 25 ms 640 KB
1_04 31 ms 908 KB
1_05 25 ms 640 KB
1_06 31 ms 888 KB
1_07 26 ms 640 KB
1_08 35 ms 1092 KB
1_09 29 ms 896 KB
1_10 41 ms 1120 KB
1_11 30 ms 908 KB
1_12 44 ms 1184 KB
1_13 36 ms 1156 KB
1_14 50 ms 1492 KB
1_15 42 ms 1496 KB
1_16 58 ms 1596 KB
1_17 42 ms 1504 KB