Submission #1128994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128994		Mike_Vu	Knapsack (NOI18_knapsack)	C++17	100 / 100	37 ms	1608 KiB

knapsack

///problem: https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 2005;
int s, n;
vector<pii> wgr[maxn];

namespace sub5{
    ll dp[maxn];
    void addval(ll v, int w) {
//        cout << v << ' ' << w << "\n";
        for (int i = s-w; i >= 0; i--) {
            maximize(dp[i+w], dp[i]+v);
        }
//        for (int i = 0; i <= s; i++) {
//            cout << (dp[i] < 0 ? -1 : dp[i]) << ' ';
//        }
//        cout << "\n";
    }
    void consbit(ll v, int w, int cnt) {
//        cout << "consbit " << v << ' ' << w << ' ' << cnt << "\n";
        int j = 0;
        while (MASK(j+1)-1 <= cnt) {
            addval(v*MASK(j), w*MASK(j));
            ++j;
        }
        if (cnt > MASK(j)-1) {
            addval(v*(cnt-MASK(j)+1), w*(cnt-MASK(j)+1));
        }
    }
    void solve() {
        memset(dp, -0x3f, sizeof(dp));
        dp[0] = 0;
        for (int i = 1; i <= s; i++) {
            sort(ALL(wgr[i]), greater<pii>());
            int numcan = s/i;
            for (pii e : wgr[i]) {
                int cnt = min(e.se, numcan);
                numcan -= cnt;
                consbit(e.fi, i, cnt);
                //remember to break
                if (numcan <= 0) break;
            }
        }
        ll ans = 0;
        for (int i = 0; i <= s; i++) {
            maximize(ans, dp[i]);
        }
        cout << ans;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    cin >> s >> n;
    for (int i= 1; i <= n; i++) {
        int v, w, k;
        cin >> v >> w >> k;
        wgr[w].pb({v, k});
    }
    return sub5::solve(), 0;
}

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