제출 #1320947

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320947		brinleyhong	Knapsack (NOI18_knapsack)	C++20	29 / 100	1 ms	332 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

}
void sub4() {

}
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: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27