Submission #812548

#	Time	Username	Problem	Language	Result	Execution time	Memory
812548		Aquarius	Knapsack (NOI18_knapsack)	C++17	0 / 100	38 ms	31804 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define show cerr<<"*\n"
using namespace std;
void debug_out() {cout << '\n';}
template <typename Head, typename ...Tail>
void debug_out(Head H, Tail ...T){
   cout << H << ' ';
   debug_out(T...);
}
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)



void solve() {
    int w, v, k, n, s; cin >> s >> n;
    vector<vector<pair<int,int>>> shop(s+5);
    vector<vector<ll>> dp(s+5, vector<ll>(s+5, INT_MIN));
    for(int i=0; i<n; i++) {
        cin >> v >> w >>k;
        if(w>s||k<=0) continue;
        shop[w].push_back({v, k});
    }
    dp[0][0]=0;
    for(int w=1; w<=s; w++) {
//        if(!sz(shop[w])) continue;
        sort(all(shop[w]), greater<pair<int,int>>());
        for(int i=1; i<=s; i++) {
            dp[i][w]=dp[i][w-1];
            int num =0, atp=0, ks=0;
            ll gia=0;
            while((num+1)*w<=i&&atp<sz(shop[w])) {
                num++;
                ks++;
                gia+=shop[w][atp].first;
                if(dp[i-num*w][w-1]!=INT_MIN) {
//                    debug(i, num , w);
                    dp[i][w]=max(dp[i][w], dp[i-num*w][w-1]+gia);
                }
                if(ks==shop[w][atp].second) {
//                    debug(gia);
                    atp++;
                    ks=0;
                }
            }
        }
    }
    ll ans =0;
    for(int i=1; i<=s; i++) {
        for(int j=1; j<=s; j++) ans = max(ans, dp[i][j]);
    }

    cout<< ans<<'\n';
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
//    cin >> T;
    while(T--)
        solve();
}

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