oj.uz

Submission #499928

# Submission time Handle Problem Language Result Execution time Memory
499928 2021-12-30T04:45:58 Z AnYandEvery Knapsack (NOI18_knapsack) C++17
12 / 100
 1 ms 296 KB 
/*
NOI: https://oj.uz/problem/view/NOI18_knapsack
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//idea 1: Ki beyond 2000 is the same as Ki of 2000
struct product{
    int worth; int weight; int num;
    void init(int w, int w2, int n){
        worth = w;
        weight = w2;
        num = n;
    }
};
//n<=1e5, ki <= 1e9, s <= 2000
int main(){
    int s, n; cin >> s >> n;
    product products[n];
    for(int i = 0; i < n; i++){
        int a, b, c; cin >> a >> b >> c;//worth, weight, numCopies 
        if(c>2000)c=2000;
        product temp; temp.init(a, b, c);
        products[i] = temp;
    }
    ll dp[s+1]; for(auto & i : dp)i = 0;
    for(int i = 0; i < n; i++){
        int numUse[s+1]; for(auto & zaa : numUse)zaa = 0;
        for(int x = 0; x < s; x++){
            int curW = products[i].weight + x;
            if(curW > s)continue;
            if(dp[x]==0&&x!=0)continue;
            if(numUse[x] == products[i].num)continue;
            ll cur = dp[x] + products[i].worth;
            ll prev = dp[curW];
            if(cur > prev){
                numUse[curW] = numUse[x] + 1;
                dp[curW] = cur;
            }
            if(cur == prev){
                numUse[curW] = min(numUse[x]+1, numUse[curW]);
            }
        }
    }
    ll mx = 0;
    for(auto & i : dp){
        if(i > mx)mx = i;
    }
    cout << mx << endl;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 292 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 292 KB Output is correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Halted 0 ms 0 KB -