Submission #989907

#	Time	Username	Problem	Language	Result	Execution time	Memory
989907		Sang	Knapsack (NOI18_knapsack)	C++14	100 / 100	52 ms	5212 KiB

knapsack

// Created by Sang lớp 9
// Какого черта ты переводишь?
#include <bits/stdc++.h>
using namespace std;
#define Sang 1
#define int long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define FOR(i, a, b) for(__typeof(b) i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for(__typeof(a) i = a, _b = b; i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int MOD = 1e9+7;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

template <class T> bool minimize(T &a, T b) { if (a > b) { a = b; return true; } return false;}

template <class T> bool maximize(T &a, T b) { if (a < b) { a = b; return true; } return false;}

//   ****   ****
//  *     *     *
//  *    K.B    *
//    *       *
//       * *  

int S, n, dp[2005];
priority_queue<ii> Q[2005];
vector<ii> items;

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
    #ifndef Sang
        freopen("main.inp", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif
    cin >> S >> n;
    FOR (i, 1, n){
        int v, w, k; cin >> v >> w >> k;
        Q[w].push({v, k});
    }
    FOR (i, 1, S){
        int cnt = 0;
        while (!Q[i].empty()){
            auto T = Q[i].top(); Q[i].pop();
            while (T.se && cnt < S/i){
                cnt++;
                T.se--;
                items.pb({i, T.fi});
            }
        }
    }
    for (auto &x : items){
        FORD(i, S, x.fi){
            maximize(dp[i], dp[i-x.fi] + x.se);
        }
    }
    cout << dp[S];

    return 0;
}

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