Submission #780472

#	Time	Username	Problem	Language	Result	Execution time	Memory
780472		christinelynn	Knapsack (NOI18_knapsack)	C++17	100 / 100	77 ms	36300 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int        long long
#define all(a)     (a).begin(), (a).end()
#define pb         push_back
#define mk         make_pair
#define pii        pair<int, int>
#define ff         first
#define ss         second
#define inp_v(vec) for (auto &i : vec) cin >> i;
#define prt_v(vec) for (auto i : vec) cout << i << endl;
#define MS(x)     memset(x, 0, sizeof(x))
#define gcd(a,b)   __gcd(a, b);
#define lcm(a,b)   (a*(b/gcd(a,b)))
#define lb         lower_bound
#define ub         upper_bound
bool chmin(int &a, int b){return b<a?a=b, true:false;}
bool chmax(int &a, int b){return b>a?a=b, true:false;}
bool comp(const pair<int, int>&a, const pair<int, int>&b){
    return a.first>b.first;
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, M;cin>>N>>M;
    int dp[N+1][N+1];
    vector<vector<pair<int,int>>>simp(N+5), v(N+5);
    for(int i=0;i<M;i++){
        int a, b, c;
        cin>>a>>b>>c;
        simp[b].push_back({a, c});
    }
    for(int i=1;i<=N;i++){
        if(!simp[i].size())continue;
        sort(simp[i].begin(), simp[i].end(), comp);
        int cost=0, val=0;
        bool stat=true;
        v[i].push_back({0, 0});
        for(auto j:simp[i]){
            if(!stat)break;
            for(int k=0;k<j.second;k++){
                cost+=i;
                val+=j.first;
                // cout<<cost<<" "<<val<<endl;
                if(cost>N){
                    stat=false;
                    break;
                }
                v[i].push_back({val, cost});
            }
        }
    }
    memset(dp, 0, sizeof(dp));
    for(int i=1;i<=N;i++){
        if(v[i].size()){
            for(auto j:v[i]){
                for(int k=0;k<=N;k++){
                    if(k>=j.second){
                        dp[i][k]=max({dp[i][k], dp[i-1][k], dp[i-1][k-j.second]+j.first});
                    }
                    else{
                        dp[i][k]=max(dp[i][k], dp[i-1][k]);
                    }
                }
            }
        }
        else{
            for(int k=0 ;k<=N;k++){
                dp[i][k]=dp[i-1][k];
            }
        }
    }
    cout<<dp[N][N]<<endl;
    return 0;
}

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