Submission #780361

#	Time	Username	Problem	Language	Result	Execution time	Memory
780361		devariaota	Knapsack (NOI18_knapsack)	C++17	12 / 100	21 ms	31724 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;
        for(auto j:simp[i]){
            if(!stat)break;
            int temp=j.second;
            for(int k=0;k<temp;k++){
                cost+=i;
                val+=j.first;
                // cout<<cost<<" "<<val<<endl;
                if(cost>N){
                    stat=false;
                    break;
                }
                v[i].push_back({val, cost});
            }
        }
    }
    for(int i=0;i<=N;i++)dp[0][i]=0;
    for(int i=1;i<=N;i++){
        dp[i][0]=dp[i-1][0];
        if(v[i].size()){
            for(auto j:v[i]){
                for(int k=1;k<=N;k++){
                    // cout<<k<<endl;
                    if(k>=j.second){
                        dp[i][k]=max(dp[i-1][k], dp[i-1][k-j.second]+j.first);
                        // cout<<i<<" "<<k<<" "<<dp[i][k]<<" "<<dp[i-1][k-j.second]<<endl;
                    }
                    else{
                        dp[i][k]=max(dp[i][k], dp[i-1][k]);
                    }
                }
            }
        }
        else{
            for(int k=1;k<=N;k++){
                dp[i][k]=dp[i-1][k];
                // cout<<i<<" "<<k<<" "<<dp[i][k]<<" "<<dp[i-1][k]<<" "<<i-1<<" "<<k<<endl;
            }
        }
    }
    cout<<dp[N][N]<<endl;
    // dp[0][0]=0;
    // for(int i=1;i<=N;i++){
    //     if(tot[i]){
    //         for(int j=1;j<=N;j++){
    //             int idx=1, cur=v[i][idx].first, cur2=v[i][idx].second, sz=v[i].size();
    //             int k=0;

                
    //         }
    //     }
    // }
    return 0;
}

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