제출 #1255212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255212		msiyem	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	4936 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define sz(x) (int)x.size()
#define f(i,a,n) for(ll i=a; i<=n; i++)
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

#define mem(a, b) memset(a, b, sizeof(a))
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
#define file() freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

ll gcd(ll a, ll b) { return __gcd(a, b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }

int dx[] = {0, 0, +1, -1, -1, +1, -1, +1};
int dy[] = {+1, -1, 0, 0, -1, +1, +1, -1};

// *******start******

const int MAXN = 100004;
const int MAXS = 2004;

int s, n, w[MAXN];
ll v[MAXN], k[MAXN], dp[MAXS];
priority_queue<pair<ll, ll>> pq[MAXS];

int main() {
    optimize();

    cin >> s >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i] >> k[i];
        pq[w[i]].push({v[i], k[i]});
    }

    for (int wt = 1; wt <= s; wt++) {
        ll cnt = s / wt;

        while (!pq[wt].empty() && cnt > 0) {
            auto [val, qty] = pq[wt].top();
            pq[wt].pop();

            ll use = min(cnt, qty);
            cnt -= use;

            // Apply 0/1 knapsack use times
            for (ll t = 0; t < use; t++) {
                for (int j = s; j >= wt; j--) {
                    dp[j] = max(dp[j], dp[j - wt] + val);
                }
            }
        }
    }

    ll ans = 0;
    f(i, 1, s) ans = max(ans, dp[i]);
    cout << ans << endl;

    return 0;
}

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