Submission #773327

#	Time	Username	Problem	Language	Result	Execution time	Memory
773327		HD1	Knapsack (NOI18_knapsack)	C++14	100 / 100	102 ms	9652 KiB

knapsack

//we are all lost trying to be someone.
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define sz(x) ll(x.size())
#define reve(x) reverse(x.begin(),x.end())
#define ff first
#define ss second
#define pb push_back
using namespace std;
#define trace(...) fff(#__VA_ARGS__, __VA_ARGS__)
template<typename t> void fff(const char* x, t&& val1) { cout<<x<< " : "<<val1<<"\n";}
template<typename t1, typename... t2> void fff(const char* x, t1&& val1, t2&&... val2){
    const char* xd=strchr(x+1, ',');
    cout.write(x, xd-x)<<" : "<<val1<<" | ";
    fff(xd+1, val2...);
}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ll, ii >tri;
const ll MAX=1e5+100;
const ll mod=1e9+7;
const ll inf=1e9;
ll dp[3][MAX];
vector<ii> s[MAX];
ll V[MAX], W[MAX];
void solve(){
   ll S, n;
   cin>>S>>n;
   for(ll i=1; i<=n; i++){
        ll v,w,k;
        cin>>v>>w>>k;
        s[w].push_back({v,k});
   }
   ll ns=1;
   for(ll i=S; i>=1; i--){
        sort(s[i].rbegin(),s[i].rend());
        ll aux=S/i;
        for(ll j=0; j<sz(s[i]); j++){
            ll k=s[i][j].ss;
            while(aux and k){
                V[ns]=s[i][j].ff;
                W[ns]=i;
                ns++;
                aux--;
                k--;
            }

        }
   }
   memset(dp, -1, sizeof dp);
   dp[0][0]=0;
   for(ll i=1; i<=ns; i++){
    for(ll j=0; j<=S; j++){
        dp[i&1][j]=dp[(i-1)&1][j];
        if(j-W[i]>=0 and dp[(i-1)&1][j-W[i]]!=-1){
            dp[i&1][j]=max(dp[i&1][j],dp[(i-1)&1][j-W[i]]+V[i]);
        }
        dp[i&1][j]=max(dp[i&1][j],dp[i&1][j-1]);
    }
   }
   cout<<dp[ns&1][S]<<'\n';
}
int main(){
    fastio;
     solve();
    return 0;
}

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