제출 #1282934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282934		peanut	Knapsack (NOI18_knapsack)	C++20	100 / 100	42 ms	1604 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

struct item
{
    int v, w, a;
} items[maxn];
int s, n;
ll dp[2005];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> s >> n;
    for (int i = 1; i <= n; ++i) cin >> items[i].v >> items[i].w >> items[i].a;

    sort(items + 1, items + 1 + n, [](item &a, item &b) {return a.w == b.w ? a.v > b.v : a.w < b.w;});

    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (items[i].w != items[i-1].w) cnt = s / items[i].w;
        for (int j = 1; j <= min(cnt, items[i].a); ++j)
        {
            for (int k = s; k >= items[i].w; --k) dp[k] = max(dp[k], dp[k-items[i].w] + items[i].v);
        }
        cnt -= min(cnt, items[i].a);
    }
    cout << *max_element(dp, dp+s+1);
    return 0;
}

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