Submission #1133891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133891		Chal1shkan	Knapsack (NOI18_knapsack)	C++20	73 / 100	1094 ms	1608 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)1e6 + 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];
int dp[2][maxn];

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]);
    }
    bool cur = 1, prev = 0;
    for (int i = 1; i <= n; ++i) {
        for (int c = 1; c <= a[i][2]; ++c) {
            for (int j = s; j >= 0; --j) {
                dp[cur][j + a[i][1] * c] = max(dp[cur][j + a[i][1] * c], dp[prev][j] + a[i][0] * c);
                dp[cur][j] = max(dp[cur][j], dp[prev][j]);
            }
        }
        swap(prev, cur);
        for (int j = 0; j <= s; ++j) {
            dp[cur][j] = 0;
        }
    }
    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: 0 / 27