Submission #781273

#	Time	Username	Problem	Language	Result	Execution time	Memory
781273		makanhulia	Knapsack (NOI18_knapsack)	C++17	73 / 100	3 ms	3616 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
const ll INF = 1e9; //4e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e2 + 5;
const ll LOG = 30; //20;
const double EPS = 1e-9;
#define vi vector <int>
#define vll vector <ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ipi pair <int, pii>
#define lpl pair <ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define apaaja                          ios_base::sync_with_stdio(0);       cin.tie(0);                         cout.tie(0);                    
ll t, n;
pll a [MAXN];
ll dp [2005][MAXN];
ll mx [2005];
ll frek [2005][MAXN];

int main(){
    apaaja
    cin >> t >> n;
    for(ll i = 1; i <= n; i++){
        ll l, e, k;
        cin >> l >> e >> k;
        a[i] = mp(l, e);
        frek[0][i] = k;
    }
    for(ll i = 1; i <= t; i++){
        mx[i] = mx[i-1];
        ll pake = 0;
        for(ll j = 1; j <= n; j++){
            frek[i][j] = frek[i-1][j];
            if(i - a[j].se >= 0 && frek[i-a[j].se][j] > 0){
                // cout << dp[i][j] << " << " << mx[-a[i].se] << " << " << a[i].fi << endl;
                dp[i][j] += mx[i-a[j].se] + a[j].fi;
            }
            if(dp[i][j] > mx[i]){
                mx[i] = dp[i][j];
                pake = j;
            }
        }
        if(pake != 0){
            for(ll j = 1; j <= n; j++){
                frek[i][j] = frek[i-a[pake].se][j];
            }
            frek[i][pake]--;
        }
        // cout << i << " ___" << mx[i] << endl;
        // cout << dp[i][pake] << " << " << pake << " << " << a[pake].fi << endl;
    }
    cout << mx[t] << endl;
}

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