Submission #860269

#	Time	Username	Problem	Language	Result	Execution time	Memory
860269		Darren_Yang	Knapsack (NOI18_knapsack)	C++14	49 / 100	1051 ms	464 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define str string

// pairs
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pd pair<ld, ld>
#define mp make_pair
#define f first
#define s second

// vectors
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rs resize
#define is insert
#define pb push_back
#define eb emplace_back
#define fr front()
#define bk back()

#define lb lower_bound
#define ub upper_bound

// loops
#define FOR(n) for(int i=0; i<(n); ++i)
#define FOR1(a, b) for(int i=(a); i<(b); ++i)
#define each(x, a) for(auto& x : a)

const int S=2e3;
ll s, n, v, w, k, dp[S+1];

void solve() {
    cin >> s >> n;
    if(n==1) {
        cin >> v >> w >> k;
        cout << v*min(s/w, k) << "\n";
    } else {
        FOR(n) {
            cin >> v >> w >> k;
            for(int j=0; j<k; ++j)
                for(int l=s; l-w>=0; --l)
                    dp[l]=max(dp[l-w]+v, dp[l]);
        }
        cout << dp[s] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();

    return 0;
}

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