제출 #1250266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250266		goldenbull	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	328 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = uint64_t;

const char el = '\n';
const int maxn = 1e5+7;
const int maxw = 2007;

int n, W;
ll v[maxn], w[maxn], k[maxn];
ll dp_val[2][maxw], dp_cnt[2][maxw];

template<typename T>
void print(T a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << el; }

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
//    freopen(".inp", "r", stdin);
//    freopen(".out", "w", stdout);

    cin >> W >> n;
    for (int i = 1; i <= n; i++) cin>>v[i], cin>>w[i], cin>>k[i];

    for (int i = 1; i <= n; i++) {
        int cur = i&1;
        int prev = cur^1;
        fill(dp_val[cur], dp_val[cur]+W+1, 0);
        fill(dp_cnt[cur], dp_cnt[cur]+W+1, 0);

        for (int j = 0; j <= W; j++) {
            ll x=0, y=0;
            ll cnt1=0, cnt2=0;
            x = dp_val[prev][j];

            if (j >= w[i]) {
                y = dp_val[cur][j - w[i]];
                cnt1 = dp_cnt[cur][j - w[i]];
                if (cnt1 < k[i]) y += v[i], cnt1++;
            }

            if (y > x) {
                dp_val[cur][j] = y;
                dp_cnt[cur][j] = cnt1;
            } else {
                dp_val[cur][j] = x;
                dp_cnt[cur][j] = cnt2;
            }
        }

//        cout << el;
//        cout << "prev: \n";
//        print(dp_val[prev], W+1);
//        print(dp_cnt[prev], W+1);
//        cout << "cur:\n";
//        print(dp_val[cur], W+1);
//        print(dp_cnt[cur], W+1);
    }

    ll res = 0;
    for (int i = 0; i <= W; i++) res = max(res, dp_val[n&1][i]);
    cout << res;

//    cout << el;
//    print(dp_val[n&1], W+1);
//    print(dp_cnt[n&1], W+1);

    return 0;
}

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