제출 #1195363

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195363		lukasuliashvili	Knapsack (NOI18_knapsack)	C++17	100 / 100	87 ms	28740 KiB

knapsack

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i,a,b) for(int i=a; i<=b; i++) 
#define fs first 
#define sc second 
#define pb push_back
const int N=1e6+3;
const int R=2002;
int a[N],v[N],w[N],k[N],dp[N];
vector<pair<int,int>> vec[N],vec1;
signed main(){
    int n,s; cin>>s>>n;
    rep(i,1,n){cin>>v[i]>>w[i]>>k[i]; vec[w[i]].pb({v[i],k[i]});}
    rep(i,1,s){
        sort(vec[i].begin(),vec[i].end());
        reverse(vec[i].begin(),vec[i].end());
        int sum=0;
        for(int j=0; j<vec[i].size(); j++){
            int k1=vec[i][j].sc;
            int v1=vec[i][j].fs;
            int pow=1;
            while(sum<s and k1>0){
                if(k1-pow<0){
                    vec1.pb({k1*i,k1*v1});
                    break;
                }
                k1-=pow;
                sum+=i*pow;
                vec1.pb({pow*i,pow*v1});
                pow++;

                

            }
        }
        for(int i1=0; i1<vec1.size(); i1++){
            for(int j1=s; j1>=vec1[i1].fs; j1--){
                dp[j1]=max(dp[j1],dp[j1-vec1[i1].fs]+vec1[i1].sc);
            }
        }
        vec1.clear();


    }
   
   
    // for(int kl=1; kl<=n; kl++){
    //     for(int i=0; i<vec[kl].size(); i++){
    //         for(int j=s; j>=vec[kl][i].sc; j--){
    //             dp[j]=max(dp[j-vec[kl][i].sc]+vec[kl][i].fs,dp[j]);
    //         }
    //     }
    // }
    cout<<dp[s]<<endl;
    

}

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