Submission #1133896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133896		Chal1shkan	Knapsack (NOI18_knapsack)	C++20	100 / 100	319 ms	2968 KiB

knapsack

# include <bits/stdc++.h>
using namespace std;
 
# define ll long long
# define ld long double
# define pii pair <int, int>
# define pll pair <ll, ll>
# define nl '\n'
# define sz(x) (int)(x).size()
# define all(x) (x).begin(), (x).end()
# define deb(x) cerr << #x << " = " << x << endl;
# define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

const int maxn = (int)1e5 + 3;
const ll inf = (ll)1e9 + 0;
const int mod = (int)1e9 + 7;
const bool T = 0;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int s, n;
array<int, 3> a[maxn];
vector <pii> v[2002];
int dp[2][2002];

void ma1n () {
    cin >> s >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][2] = min(a[i][2], s / a[i][1]);
        v[a[i][1]].push_back({a[i][0], a[i][2]});
    }
    bool cur = 1, prev = 0;
    for (int i = 1; i <= s; ++i) {
        sort(all(v[i]), greater<pii>());
        for (int x = 0; x <= s; ++x) {
            int c = 0, sum = 0;
            for (int j = 0; j < sz(v[i]); ++j) {
                int pnt = 0;
                while ((c + 1) * i <= x && pnt < v[i][j].second) {
                    c++;
                    pnt++;
                    sum += v[i][j].first;
                    dp[cur][x] = max(dp[cur][x], dp[prev][x - c * i] + sum);    
                }
            }
        }
        for (int j = 0; j <= s; ++j) {
            dp[cur][j] = max(dp[cur][j], dp[prev][j]);
            dp[prev][j] = 0;
        }
        swap(prev, cur);
    }
    cout << dp[prev][s] << nl;
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int ttt = 1;
    if (T) cin >> ttt;
    while (ttt--) {
        ma1n();
    }
    return 0;
}

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