Submission #975812

#	Time	Username	Problem	Language	Result	Execution time	Memory
975812		vjudge1	Knapsack (NOI18_knapsack)	C++98	100 / 100	173 ms	141356 KiB

knapsack

#include <bits/stdc++.h>
using  namespace std;
int s,n;
int banyak=0;
vector<int>value,weight;
void solve(){
    int dp[banyak+1][s+1];
    for (int i = 0; i <= s; i++)
    {
        dp[0][i]=0;
    }
    for (int i = 0; i <= banyak; i++)
    {
        dp[i][0]=0;
    }
    for (int i = 1; i <= banyak; i++)
    {
        for (int j = 1; j <= s; j++)
        {
            if(weight[i]>j){
                dp[i][j]=dp[i-1][j];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            }
        }
    }
    cout<<dp[banyak][s];
}
int main(){
    cin>>s>>n;
    vector<pair<int,int>> A[2006];
    weight.push_back(0);
    value.push_back(0);
    for (int i = 0; i < n; i++)
    {
        int v,w,k;
        cin>>v>>w>>k;
        A[w].push_back(make_pair(v,k));
    }
    for (int w = 1; w <= 2005; w++)
    {
        sort(A[w].begin(),A[w].end());
        int used=2005/w+1;
        while (used!=0&&!A[w].empty())
        {
           value.push_back(A[w].back().first);
           weight.push_back(w);
            banyak++;
            A[w].back().second--;
            used--;
            if(A[w].back().second==0){
                A[w].pop_back();
            }
        }
        
    }
    solve();
}

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