Submission #975468

#	Time	Username	Problem	Language	Result	Execution time	Memory
975468		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	107 ms	262144 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long

int s, n;
struct Cake{
    int v, w, k;
};
Cake cake[100003];
int memo[100003][2003];

int binser(int l, int r, int we, int idx){
    if(l > r){
        return 0;
    }
    if(idx == n + 1){
        return 0;
    }
    int &res = memo[idx][we];
    if(res != -1) return res;
    int ans = binser(0, cake[idx + 1].k, we, idx + 1);
    int mid = (l+r)/2;
    int val = mid * cake[idx].w;
    if(val <= we) ans = max(ans, cake[idx].v*mid + binser(0, cake[idx + 1].k, we - cake[idx].w*mid, idx + 1));
    ans = max(ans, max(binser(l, mid - 1, we, idx), binser(mid + 1, r, we, idx)));
    return res = ans;
}

signed main(){
    memset(memo, -1, sizeof memo);
    cin >> s >> n;
    for(int i = 1; i<=n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        cake[i].v = x;
        cake[i].w = y;
        cake[i].k = z;
    }
    cout << binser(0, cake[1].k, s, 1);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27