제출 #1274604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274604		priyansh_16	Knapsack (NOI18_knapsack)	C++20	100 / 100	147 ms	84948 KiB

knapsack

#include<iostream>
#include<algorithm>
#include <string>
#include<iomanip>
#include <map>
#include<vector>
#include <cmath>
#include<set>
#include<stack>
#include<queue>
#include <list>
#include<cstring>
#include<unordered_set>
#include<unordered_map>
#include<utility>
using namespace std;
#define int long long
#define pb push_back
int m1=1e9+7;
int m2=998244353;
int binpow(int a,int b,int m){
    int ans=1;
    while(b>0){
        int r=b%2;
        if(r&1){
            ans*=a;
            ans%=m;
        }
        a*=a;
        a%=m;
        b/=2;
    }
    return(ans);
}
vector<int> fac(1e7+10);
void factorial(){
    fac[0]=1;
    for(int i=1;i<=1e7+9;i++){
        fac[i]=fac[i-1]*i;
        fac[i]%=m1;
    }
}
void dfs(int node,vector<vector<int>>&ar,vector<int>&vis,vector<int>&par){
    vis[node]=1;
    for(auto it:ar[node]){
        if(vis[it]==0){
            vis[it]=1;
            par[it]=node;
            dfs(it,ar,vis,par);
        }
    }
}
signed main(){
    cout<<setprecision(50);
    int t=1;
    //cin>>t;
    for(int i=0;i<t;i++){
        int s,n;
        cin>>s>>n;
        vector<vector<int>> vf;
        for(int i=0;i<n;i++){
            int v,w,k;
            cin>>v>>w>>k;
            vector<int> vtemp;
            vf.pb({w,v,k});
        }
        sort(vf.begin(),vf.end());
        map<int,int>mp;
        vector<vector<int>> v;
        for(int i=n-1;i>=0;i--){
            int val= vf[i][1];
            int weight=vf[i][0];
            int k=min(vf[i][2],(s-mp[weight]*weight)/weight);
            mp[weight]+=k;
            if(k==0){
                continue;
            }
            v.push_back({weight,val,k});
        }
        // for(auto it:v){
        //     cout<<it[0]<<" "<<it[1]<<' '<<it[2]<<'\n';
        // }
        vector<int> dp(s+1,-1);
        dp[0]=0;
        for(auto it:v){
            for(int j=0;j<it[2];j++){
                for(int i=s-it[0];i>=0;i--){
                    if(dp[i]!=-1){
                        //cout<<":";
                        dp[i+it[0]]=max(dp[i+it[0]],dp[i]+it[1]);
                        //cout<<dp[i+it[0]]<<" ";
                    }
                }
            }
        }
        int mx=0;
        for(int i=0;i<=s;i++){
            mx=max(mx,dp[i]);
        }
        cout<<mx<<'\n';
    }
}

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