Submission #474839

#	Time	Username	Problem	Language	Result	Execution time	Memory
474839		BackNoob	Knapsack (NOI18_knapsack)	C++14	73 / 100	1083 ms	3892 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define mask(i) (1LL << (i))
#define task "name"
#define ull unsigned long long
using namespace std;
const ll mxN = 220797 + 7;
const ll inf = 1e9 + 277;
const ll mod = 2147483648;
const ll infll = 1e18 + 7;
const ll base = 307;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}

struct item{
	ll v , w , k;
} a[mxN];

ll dp[3000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("task.inp" , "r" , stdin);
    //freopen("task.out" , "w" , stdout);
    
    int s , n;
    cin >> s >> n;
    for(int i = 1 ; i <= n ; i++) cin >> a[i].v >> a[i].w >> a[i].k;

    for(int j = 1 ; j <= n ; j++)
    for(int i = s ; i >= 0 ; i--)
    for(int sz = 1 ; sz <= a[j].k && a[j].w * sz <= i ; sz++) {
    	if(maximize(dp[i] , dp[i - a[j].w * sz] + sz * a[j].v) == true && i == 3) {
    	}
    }

    //for(int i = 1 ; i <= s ; i++) cout << dp[i] << endl;

    cout << dp[s] << endl;

    return 0;
}

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