Submission #1260517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260517		settop	Knapsack (NOI18_knapsack)	C++20	73 / 100	1096 ms	676 KiB

knapsack

#include<bits/stdc++.h>
 
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define int long long 
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
#define eb emplace_back
#define S second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define F first
#define fall(i,a,n) for(int i=a;i<=n;i++)
#define rfall(i,a,n) for(int i=a;i>=n;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define lsb(x) (x & -x)
#define sz(x) (int)x.size()
const int MAXN=2e3+10;
const int MAXL=1e5+10;
const int inf=1e18;
const int MOD=1e9+7;
 
typedef pair<int,int> pii;
typedef tuple<int,int,int>trio;
typedef tuple<int,int,int,int> squad;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k,dp[MAXN],tira[MAXN],aux[MAXN];
multiset<int> st[MAXN];

int32_t main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("odometer.in","r",stdin);
    //freopen("odometer.out","w",stdout);

    cin>>k>>n;

    fall(i,1,k) dp[i]=-inf;
    
    int ans=0;
    fall(i,1,n){
        int val,p,q; cin>>val>>p>>q;
        fall(j,0,k) st[j].clear(),tira[j]=0;

        rfall(j,k,1){
            if(j!=k && (j%p)==(k%p)) break;
            int px=1;
            while(px<q && p*px<=j) st[j%p].insert(dp[j-p*px]+val*px),aux[j-p*px]=dp[j-p*px]+val*px,px++;
        }

        rfall(j,k,1){
            if(j>=p*q) st[j%p].insert(dp[j-p*q]+q*val+tira[j%p]),aux[j-p*q]=dp[j-p*q]+q*val+tira[j%p];
            if(st[j%p].size()>0){
                auto x=*st[j%p].rbegin();
                dp[j]=max(dp[j],x-tira[j%p]);
                tira[j%p]+=val;
                st[j%p].erase(st[j%p].find(aux[j-p]));
            }
        }
    }
    fall(i,1,k) ans=max(ans,dp[i]);
    cout<<ans<<"\n";
}

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