Submission #1172310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172310		nagibator	Knapsack (NOI18_knapsack)	C++20	0 / 100	0 ms	324 KiB

knapsack

#include <bits/stdc++.h>
#define nn '\n'
#pragma GCC optimize("O3")
#define int long long
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
#define all(x) x.begin(), x.end()
#define sec second
#define vec std::vector
const int N = 2005;
using namespace std;
vec<pair<int, int>> v;
int dp[N];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    v.pb({0, 0});
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.pb({a, b});
    }
    for (int i = 1; i < v.size(); i++) {
        for (int j = n; j >= v[i].first; j--) {
            dp[j] = max(dp[j], dp[j - v[i].first] + v[i].second);
        }
    }
    cout << dp[n] << nn;
}

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