Submission #1110597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110597		Mike_Vu	Knapsack (NOI18_knapsack)	C++14	100 / 100	30 ms	1828 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITJ(x, j) (((x)>>(j))&1)

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;
ll ans = 0;

namespace sub5{
    vector<pii> wgr[maxn];
    ll dp[maxn];
    void additem(ll v, int w) {
//        cout << "item " << 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 << i << ' ' << dp[i] << "\n";
//        }
    }
    void consbit(int v, int w, int k) {
        int sum;
        for (sum = 1; sum*2-1 <= k; sum <<= 1) {
            additem((ll)v*sum, w*sum);
            if (k-(sum*2-1) < sum*2) break;
        }
        int val = k-(sum*2-1);
        if (val > 0) {
            additem((ll)v*val, w*val);
        }
    }
    void solve() {
        for (int i = 1; i <= n; i++) {
            //pushback {v, k}
            int v, w, k;
            cin >> v >> w >> k;
            if (w > s) continue;
            if (w == s) {
                maximize(ans, (ll)v);
                continue;
            }
            wgr[w].pb({v, k});
        }
        memset(dp, 0, sizeof(dp));
        for (int w = 1; w < s; w++) {
            //consider wgr w
            int sumw = 0; //only before full
            sort(wgr[w].begin(), wgr[w].end(), greater<>());
            for (int i = 0; i < (int)wgr[w].size(); i++) {
                int v = wgr[w][i].fi, k = wgr[w][i].se;
                minimize(k, (s-sumw)/w);
                if (k <= 0) break;
                //solve
                consbit(v, w, k);
//                for (int j = 1; j <= k; j++) {
//                    additem(v, w);
//                }
                //another break
                sumw += k*w;
                if ((s-sumw)/w <= 0) break;
            }
        }
        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;
//    if (n == 1) return sub1::solve(), 0;
    return sub5::solve(), 0;
}
/*
6 1
8 1 7
48

15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1

20 3
5000 15 1
100 1 3
50 1 4
*/

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