Submission #1173251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173251		shrimpppppp	Knapsack (NOI18_knapsack)	C++20	49 / 100	462 ms	23972 KiB

knapsack

//Hoshino is my wife UwU

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<long long, long long> vll;
typedef vector<int, int> vii;

#define a_all(x) x + 1, x + 1+ n
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define file "test"

const int N = 1e6 + 5;
const ll inf = 1e18;
const int MID = 1e9 + 7;
const int NN = 5e3 + 5;


ll n, s, w[N], v[N], k[N], dp[N];
vector<pii> sigmaboi[N];
vector<int> wei;

void sub1(){
    if (w[1] <= s){
        ll l = 1, r = k[1], mid, rs = 0;
        for (int i=1;i<=100;i++){
            mid = (l + r)/2;
            if (mid * w[1] <= s) l = mid + 1;
            else r = mid - 1;
        }
        cout << v[1] * mid;
        exit(0);
    }
}

void sub23(){
    for (int i=1;i<=n;i++){
        for (int j=s;j>=w[i];j--){
            for (int u=1;u<=k[i];u++){
                if (j-w[i]*u >= 0) dp[j] = max(dp[j-w[i]*u] + v[i]*u, dp[j]);
            }
        }
    }
    cout << dp[s];
    exit(0);
}

void sub45(){
    for (int i=1;i<=n;i++){
        wei.pb(w[i]);
        sigmaboi[w[i]].pb({v[i], k[i]});
    }
    sort(all(wei));
    for (auto x: wei){
        sort(all(sigmaboi[x]), greater<pii>());
        for (int j=s;j>=x;j--){
            int id = 0, curr = 1, cnt  =0;
            while ((cnt + 1) * x <= j && id < sigmaboi[x].size()){
                cnt ++;
//                cout << j << ' ' << id << ' ' << x << ' ' << cnt << ' ' << curr << endl;
                dp[j] = max(dp[j], dp[j - cnt*x] + cnt * sigmaboi[x][id].fi);
                curr ++;
                if (curr >= sigmaboi[x][id].se){
                    curr = 1;
                    id ++;
                }
            }
        }
    }
//    for (int i=0;i<=s;i++){
//        cout << dp[i] << ' ';
//    }
    cout << dp[s];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> s >> n;
    ll mx = 0;
    for (int i=1;i<=n;i++){
        cin >> v[i] >> w[i] >> k[i];
        mx = max(mx, k[i]);
    }
    if (n == 1) sub1();
    if (n <= 100 && mx <= 100) sub23();
    sub45();

    return 0;
}

//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣤⡤⠤⠤⠤⣤⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡤⠞⠋⠁⠀⠀⠀⠀⠀⠀⠀⠉⠛⢦⣤⠶⠦⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⢀⣴⠞⢋⡽⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠃⠀⠀⠙⢶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⣰⠟⠁⠀⠘⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⡀⠀⠀⠉⠓⠦⣤⣤⣤⣤⣤⣤⣄⣀⠀⠀⠀
//⠀⠀⠀⠀⣠⠞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⣷⡄⠀⠀⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠻⣆⠀
//⠀⠀⣠⠞⠁⠀⠀⣀⣠⣏⡀⠀⢠⣶⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⠿⡃⠀⠀⠀⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡆
//⢀⡞⠁⠀⣠⠶⠛⠉⠉⠉⠙⢦⡸⣿⡿⠀⠀⠀⡄⢀⣀⣀⡶⠀⠀⠀⢀⡄⣀⠀⣢⠟⢦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⠃
//⡞⠀⠀⠸⠁⠀⠀⠀⠀⠀⠀⠀⢳⢀⣠⠀⠀⠀⠉⠉⠀⠀⣀⠀⠀⠀⢀⣠⡴⠞⠁⠀⠀⠈⠓⠦⣄⣀⠀⠀⠀⠀⣀⣤⠞⠁⠀
//⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⠀⠁⠀⢀⣀⣀⡴⠋⢻⡉⠙⠾⡟⢿⣅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠙⠛⠉⠉⠀⠀⠀⠀
//⠘⣦⡀⠀⠀⠀⠀⠀⠀⣀⣤⠞⢉⣹⣯⣍⣿⠉⠟⠀⠀⣸⠳⣄⡀⠀⠀⠙⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠈⠙⠒⠒⠒⠒⠚⠋⠁⠀⡴⠋⢀⡀⢠⡇⠀⠀⠀⠀⠃⠀⠀⠀⠀⠀⢀⡾⠋⢻⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇⠀⢸⡀⠸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⢠⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣇⠀⠀⠉⠋⠻⣄⠀⠀⠀⠀⠀⣀⣠⣴⠞⠋⠳⠶⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠳⠦⢤⠤⠶⠋⠙⠳⣆⣀⣈⡿⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

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