Submission #1192109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192109		Francisco_Martin	Knapsack (NOI18_knapsack)	C++20	100 / 100	70 ms	34376 KiB

knapsack

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

#define debug(v) cerr<<#v" = "<<(v)<<"\n";
#define debugvec(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<v[i]<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define debugvecp(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<"[ "<<v[i].fst<<" "<<v[i].snd<<" ]"<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define fst first
#define snd second
#define gcd(x,y) __gcd(x,y)
#define OnlineJudge(s) freopen((s".in"),"r",stdin); freopen((s".out"),"w",stdout);
#define fastIO() cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);
#define boolsolve() cout<<(solve()?"Yes":"No");

using ll=long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;

const ll INF=1e18;
const ll MOD=1e9+7;
const ll MAXN=601;

void solve(){
    ll s, n, c=1, a, b;
    cin >> s >> n;
    map<ll,vpll> A;
    for(int i=0; i<n; i++){
        cin >> a >> b >> c;
        if(b<=s) A[b].push_back({a,c});
    }
    c=1;
    vvll dp(A.size()+1,vll(s+1,-INF)); dp[0][0]=0;
    for(auto [w,B]:A){
        sort(B.begin(),B.end(), greater<pll>());
        for(int i=0; i<=s; i++){
            dp[c][i]=dp[c-1][i];
            ll cop=0, t=0, cur=0, bst=0;
            while((cop+1)*w<=i && t<B.size()){
                cop++; bst+=B[t].fst;
                if(dp[c-1][i-cop*w]!=-INF) dp[c][i]=max(dp[c][i],dp[c-1][i-cop*w]+bst);
                cur++;
                if(cur==B[t].snd){
                    cur=0;
                    t++;
                }
            }

        }
        c++;
    }
    cout << *max_element(dp.back().begin(),dp.back().end());
}

int main(){
    fastIO();
    //OnlineJudge("snakes")
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
        //cout << "\n";
    }
    return 0;
}

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