Submission #987505

#	Time	Username	Problem	Language	Result	Execution time	Memory
987505		DeadlyCritic	Knapsack (NOI18_knapsack)	C++17	73 / 100	1082 ms	2652 KiB

knapsack

#include <bits/stdc++.h>

 
#define scan(a, __n) for(int __ = 0; __ < __n; __++)cin >> a[__];
// #define print(a, __n) for(int ___ = 0; ___ < __n; ___++)cout << a[___] << ' '; cout << '\n';
//  #define int ll

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

// #define fr first
// #define sc second
 
#define all(v) v.begin(), v.end()
 
// #define c0 (v<<1)
// #define c1 (c0|1)
// #define md ((l+r)/2)
 
typedef long long ll;
typedef double ld;


using namespace std;

const int mod = 1e9+7;
const int maxN = 2007;

// const int maxFac = maxN; 
// ll fac[maxFac], _fac[maxFac];

// ll po(ll b, ll p){
//     b %= mod;
//     p %= mod-1;
//     ll r = 1;
//     while(p){
//         if(p&1)r = r*b%mod;
//         p >>= 1;
//         b = b*b%mod;
//     }
//     return r;
// }

// ll choose(ll k, ll n){
//     return fac[n]*_fac[k]%mod*_fac[n-k]%mod;
// }

// ll factorial(ll n, ll k){
//     ll ret = 1;
//     for(ll i = n; i >= n-k+1; i--){
//         ret = ret*i%mod;
//     }
//     return ret;
// }

int dp[maxN];
deque<pair<int, int>> dq[maxN];
int v, w, k;

inline void ad(int val, int i, int ind){
    while(dq[ind].size() > 0 && dq[ind].front().second <= val){
        // if(ind == 0)cout << "rem1 " << dq[0].front().first << '\n';
        dq[ind].pop_front();
    }
    dq[ind].push_front({i, val});
    // if(ind == 0)cout << "add " << dq[0].front().first << '\n';
}

inline void rem(int i, int ind){
    if(dq[ind].back().first <= i){
        // if(ind == 0)cout << "rem2 " << dq[0].back().first << '\n';
        dq[ind].pop_back();
    }
}

int lazy[maxN];
void slv(){
    int s, n;
    cin >> s >> n;
    for(int i = 0; i < n; i++){
        cin >> v >> w >> k;
        k = min(k, 3000);
        for(int i = 0, ind = 0; i <= s; i++, ind = (ind == w-1?0:ind+1)){
            ad(dp[i]-lazy[ind], i, ind);
            rem(i-w*k-w, ind);
            dp[i] = dq[ind].back().second+lazy[ind];
            lazy[ind] += v;
        }
        
        for(int i = 0; i < w; i++)dq[i].clear(), lazy[i] = 0;
    }

    cout << dp[s] << endl;
}

signed main(){
    // freopen("time.in", "r", stdin);
    // freopen("time.out", "w", stdout);

    fastIO;
    // cout << fixed << setprecision (15);


    // fac[0] = 1;
    // for(int i = 1; i < maxFac; i++)fac[i] = fac[i-1]*i%mod;
    // _fac[maxFac-1] = po(fac[maxFac-1], mod-2);
    // for(int i = maxFac-2; i >= 0; i--)_fac[i] = _fac[i+1]*(i+1)%mod;

    // w[0] = 1;
    // for(int i = 1; i < maxN; i++)w[i] = w[i-1]*p%mod;
    // _w[maxN-1] = po(w[maxN-1], mod-2);
    // for(int i = maxN-2; i >= 0; i--)_w[i] = _w[i+1]*p%mod;
    
    
    int t = 1;
    // cin >> t;
    while(t--){
        // cout << "**S" << endl;

        // cout << slv() << '\n';
        slv();
        // string s;
        // cin >> s;
        // bool x = slv();
        // cout << (x?"YES":"NO") << '\n';
    }
}       
/*

*/

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