제출 #1131028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131028		Braabebo10	Knapsack (NOI18_knapsack)	C++20	100 / 100	366 ms	66784 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
int main() {
    baraa
    ll s, n, m = 2e3 + 5;
    cin >> s >> n;
    vector<vector<ll>>w(m);
    vector<array<ll, 3>>a(n);
    for (ll i = 0; i < n; i++)
        for(ll j = 0; j < 3; j++)
            cin >> a[i][j];
    sort(all(a), greater());
    for (ll i = 0; i < n; i++)
        while(w[a[i][1]].size() < m and a[i][2]--)
            w[a[i][1]].push_back(a[i][0]);
    vector<vector<ll>>dp(m, vector<ll>(m, -1));
    function<ll(ll, ll)>solve = [&](ll i, ll rem) -> ll{
        if (rem < 0)return -1e16;
        if (i == m)return 0;
        if (dp[i][rem] != -1)return dp[i][rem];
        ll ret = solve(i + 1, rem), prf = 0, cost = 0;
        for (ll j = 0; j < w[i].size() and rem - cost + i >= 0; j++){
            prf += w[i][j];
            cost += i;
            ret = max(ret, solve(i + 1, rem - cost) + prf);
        }
        return dp[i][rem] = ret;
    };
    cout << solve(0, s);
    return 0;
}

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