제출 #904075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904075		lambd47	Knapsack (NOI18_knapsack)	C++14	100 / 100	99 ms	4960 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> dp(2001,-1);//maximo preco que conseguimos fazendo W com itens de peso ate x [x][w]

vector<pair<int,int>> pesos[2001];

int32_t main(){
    int s,n;
    cin>>s>>n;
    for(int i=0;i<n;i++){
        int v,w,k;
        cin>>v>>w>>k;
        pesos[w].push_back({v,k});
    }
    for(int i=1;i<=s;i++){
        sort(pesos[i].begin(),pesos[i].end(),greater<pair<int,int>>());
    }
    dp[0]=0;
    for(int x=1;x<=s;x++){
        int somao=0;
        for(auto a: pesos[x]){
            int val, qnts;
            int it=0;
            int qntstot=0;
            val=a.first, qnts=a.second;
            while(somao<=s && it<qnts){
                somao+=x;
                it++;
                qntstot++;
                for(int i=s;i>=1;i--){
                    if(i-x>=0){
                        if(dp[i-x]!=-1)dp[i]=max(dp[i],dp[i-x]+val);
                        //if(x==1)cout<<dp[i-x];
                    }
                }
            } 
        }
    }
   int resp=0;
   for(int i=1;i<=s;i++)resp=max(resp,dp[i]);
   cout<<resp;
}

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