Submission #1274345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274345		kiteyu	Knapsack (NOI18_knapsack)	C++20	100 / 100	38 ms	2800 KiB

knapsack

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll=long long;
const int N=1e5;
const int M=2e6;
int s,n,n1=0;
struct node{
    int v;
    int w;
    int k;
}a[N+5],b[M+5];
int dp[2005];
vector<pair<int,int>>g[2005];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i].v>>a[i].w>>a[i].k;
        g[a[i].w].push_back({a[i].v,a[i].k});
    }
    for(int i=1;i<=s;++i){
        sort(g[i].begin(),g[i].end(),greater<pair<int,int>>());
        int cur=0;
        for(int j=0;j<(int)g[i].size();++j){
            while(cur<s/i&&g[i][j].se>0){
                g[i][j].se--;
                cur++;
                for(int l=s-i;l>=0;--l)
                    dp[l+i]=max(dp[l+i],dp[l]+g[i][j].fi);
            }
        }

    }
    int ans=0;
    for(int i=0;i<=s;++i)
        ans=max(ans,dp[i]);
    cout<<ans;
    return 0;
}

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