Submission #1252681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252681		dfscp	Knapsack (NOI18_knapsack)	C++20	100 / 100	39 ms	1608 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
#define nl '\n'
#define f0(i,a,b) for (int i = a, _b = b; i < _b; i++)
#define f1(i,a,b) for (int i = a, _b = b; i <= _b; i++)
#define rf(i,a,b) for (int i = a, _b = b; i >=_b; i--)
#define fi first
#define se second
#define file(Name) freopen(Name".inp", "r", stdin); freopen(Name".out", "w", stdout);
#define Size(a) (int)a.size()
#define bit(mask, i) ((mask>>i)&1)

using namespace std;

const int Maxn = 2e3+5;
const int mod = 1e9+7;
const int inf32 = 2e9+5;
const long long inf64 = 2e18+7;

int s, n;
vector<pair<int, int>> g[Maxn];
ll f[Maxn];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("test.inp", "r", stdin); freopen("hoc.out", "w", stdout);
    cin >> s >> n;
    f1(i,1,n)
    {
        int v, w, k; cin >> v >> w >> k;
        g[w].push_back({v,k});
    }
    f1(w,1,2e3)
    {
        if (!g[w].size()) continue;
        sort(g[w].begin(), g[w].end(), greater<pair<int, int>>());
        rf(i,s,1)
        {
            int cnt = 0, pos = 0, cnt_use = 0;
            ll val = 0;
            while((cnt+1)*w <= i && pos < g[w].size())
            {
                cnt++;
                val += g[w][pos].fi;
                f[i] = max(f[i], f[i-cnt*w] + val);
                cnt_use++;
                if (cnt_use == g[w][pos].se) cnt_use = 0, pos++;
            }
        }
    }
    cout << f[s];
    return 0;
}

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