Submission #1156729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156729		21075028	Knapsack (NOI18_knapsack)	C++20	100 / 100	189 ms	17680 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int dp[2001][2001];
unordered_map<int,vector<pair<int,int>>> m;
long long func(int i,int s){
    if(i==2001) return 0;
    if(dp[i][s]!=-1)return dp[i][s];
    
    long long ans=0;
    long long val=0;
    int chk=0;
    ans=func(i+1,s);
    int cnt=1;
    for(auto p:m[i]){
        
       for(int j=1;j<=p.second;j++){
          if(cnt*i<=s){
          
              val+=p.first;
              ans=max(ans,val+func(i+1,s-cnt*i));
             
              cnt++;
          }
          else {
            chk=1;
            break;
          }
       }
       if(chk) break;
    }
    return dp[i][s]=ans;
}

int main(){
    int s,n;
    cin>>s>>n;
    for(int i=0;i<=2000;i++){
        for(int j=0;j<=2000;j++){
            dp[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        int v,w,k;
        cin>>v>>w>>k;
        m[w].push_back({v,k});
    }
    for(int i=1;i<=2000;i++){{
        sort(m[i].rbegin(),m[i].rend());
    }}
    cout<<func(1,s)<<endl;;
    
    
}

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