제출 #1320962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320962		brinleyhong	Knapsack (NOI18_knapsack)	C++20	73 / 100	14 ms	2596 KiB

knapsack

//https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000;
const int maxs = 2000;
const int maxv = 1000000;

int n;
long long s, v[maxn+5], w[maxn+5], k[maxn+5], dp[maxs+5];

void read() {
    cin >> s >> n;
    for (int i = 1; i<=n; ++i) cin >> v[i] >> w[i] >> k[i];
}
void sub1() { //N = 1
    cout << v[1] * (min(k[1], s / w[1]));
}
void sub2() {  //1<=N<=100 && K[1] = 1 ---> Knapsack 0/1
    long long res = 0;
    for (int item = 1; item <= n; ++item) {
        for (int sum = s; sum > 0; --sum) {
            if (sum < w[item]) continue;
            dp[sum] = max(dp[sum - w[item]] + v[item], dp[sum]);
        }
    }
    for (int sum = 1; sum <= s; ++sum) {
        res = max(res, dp[sum]);
    }
    cout << res;
}
void sub3() { //1<=N<=100 && 1<=k[i]<=10 ---> Bounded Knapsack
    long long res = 0;
    for (int item = 1; item <= n; ++item) {
        for (int sum = s; sum > 0; --sum) {
            if (sum < w[item]) continue;
            for (int take = 1; take <= k[item]; ++take) {
                if (take * w[item] > sum) break;
                dp[sum] = max(dp[sum - take*w[item]] + take*v[item], dp[sum]);
            }
        }
    }
    for (int sum = 1; sum <= s; ++sum) {
        res = max(res, dp[sum]);
    }
    cout << res;
}
void sub4() { //1<=N<=100 && 1<=k[i]<=1e9
    vector <long long> W, V;
    for (int i = 1; i<=n; ++i) {
        long long cnt = k[i];
        long long base = 1;
        while (cnt > 0) {
            long long take = min(base, cnt);
            W.push_back(w[i]*take);
            V.push_back(v[i]*take);
            cnt -= take;
            base <<= 1;
        }
    }

    for (int i = 0; i < W.size(); ++i) {
        for (int sum = s; sum >= W[i]; --sum) {
            dp[sum] = max(dp[sum], dp[sum - W[i]] + V[i]);
        }
    }

    cout << dp[s];
}
void sub5() {

}

void solve() {
    int g = *max_element(k+1, k+n+1);

    if (g == 1) {
        sub2();
        return;
    }

    if (n == 1) sub1();
    else if (1 <= n && n <= 100 && g == 1) sub2();
    else if (1 <= n && n <= 100 && g <= 10) sub3();
    else if (1 <= n && n <= 100 && g <= 1e9) sub4();
//    else sub5();
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}

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