제출 #812570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
812570		Aquarius	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	468 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;
    map<int, vector<pair<int,int>>> shop;
    for(int i=0; i<n; i++) {
        cin >> v >> w >>k;
        if(w>s||k<=0) continue;
        shop[w].push_back({v, k});
    }
    vector<vector<ll>> dp(s+5, vector<ll>(sz(shop)+1, INT_MIN));
    dp[0][0]=0;
    int idx=1;
    for(auto &[w, item]: shop) {
        sort(all(item), greater<pair<int,int>>());
        for(int i=1; i<=s; i++) {
            dp[i][idx]=dp[i][idx-1];
            int num =0, atp=0, ks=0;
            ll gia=0;

            while((num+1)*w<=i&&atp<sz(item)) {
                num++;
                ks++;
                gia+=item[atp].first;
//                debug(gia);
                if(dp[i-num*w][idx-1]!=INT_MIN) {
                    dp[i][idx]=max(dp[i][idx], dp[i-num*w][idx-1]+gia);
                }
                if(ks==item[atp].second) {
//                    debug(gia);
                    atp++;
                    ks=0;
                }
            }
        }
        idx++;
    }
//    debug(dp[1][1]);
    ll ans =0;
    for(int i=1; i<=s; i++) {
         ans = max(ans, dp[i][idx-1]);
    }

    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: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27