Submission #1192031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192031		bestbest	Knapsack (NOI18_knapsack)	C++20	100 / 100	59 ms	34372 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define  en '\n'
#define  sp ' '
typedef long long ll;
#define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


#define pii pair<ll,ll>

const int N=2e3+5;
const ll M=1e9+7;

int s,n;
vector<pii> v[N];
ll cnt[N][N];
ll dp[N];
ll val,wei,k;
ll mx;
int idx;

int main(){Linux
    cin >> s >> n;
    for(int i=1;i<=n;i++){
        cin >> val >> wei >> k;
        v[wei].push_back({val,k});
    }
    for(int i=1;i<=s;i++){
        sort(v[i].begin(),v[i].end(),greater<pii>());
        for(int j=0;j<v[i].size();j++){
            swap(v[i][j].first,v[i][j].second);
            if(j>0){
                v[i][j].first+=v[i][j-1].first;
            }
        }
    }

    // for(int i=1;i<=s;i++){
    //     cout << i << (i<10?" : ":": ");
    //     for(auto [count,vv]:v[i]){
    //         cout << count << ',' << vv << sp;
    //     }

    //     cout << en;
    // }



    for(int i=1;i<=s;i++){
        // cout << i << (i<10?" : ":": ");
        mx=0;
        idx=0;
        for(int j=1;j<=i;j++){
            if(v[j].empty())continue;
            if(cnt[i-j][j]==v[j].back().first)continue;
            auto it=upper_bound(v[j].begin(),v[j].end(),make_pair(cnt[i-j][j],M))-v[j].begin();
            if(it>=v[j].size()){
                // cout << j << "out ";
                continue;
            }
            // cout << "cntbef" << cnt[i-j][j] << 'j' ;
            // cout << j << ',' << it << "value" << v[j][it].second << sp;
            // cout << v[j][it].first << sp;
            if(mx<v[j][it].second+dp[i-j]){
                mx=v[j][it].second+dp[i-j];
                idx=j;
            }
        }
        // cout << "max=" << idx;
        // cout << en;
        if(mx<dp[i-1]){
            dp[i]=dp[i-1];
            for(int j=1;j<=s;j++){
                cnt[i][j]=cnt[i-1][j];
            }
            continue;
        }
        dp[i]=mx;
        for(int j=1;j<=s;j++){
            cnt[i][j]=cnt[i-idx][j];
            // cout << cnt[i][j] << sp;
        }
        cnt[i][idx]++;
    }

    // for(int i=1;i<=s;i++){
    //     cout << i << (i<10?" : ":": ");
    //     for(int j=1;j<=s;j++){
    //         cout << cnt[i][j] << sp;
    //     }
    //     cout << en;
    // }

    // for(int i=1;i<=s;i++)cout << i << sp << dp[i] << en;


    cout << dp[s] << en;
    
    
    return 0;
}

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