Submission #1269434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269434		arianshabaani	Knapsack (NOI18_knapsack)	C++20	49 / 100	326 ms	1868 KiB

knapsack

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

// #CONFIG
string outone = "SUCCESS";
string outtwo = "IMPOSSIBLE";

const int inf=1e9;
const int mod=1e9+7;
const int maxn25=2*1e5+10;
const int maxn55=5*1e5+10;
const int maxn5=1e5+10;
const int maxn7=1e7+10;
const int maxn9=1e9+10;

#define ll long long int
#define ull unsigned long long int
#define pass cerr << "Pass shod!" << endl
#define testc ll tt; cin >> tt; while(tt--)
#define pb push_back
#define mp(i, j) make_pair(i, j)
#define migmig cin.tie(0); cout.tie(0); ios::sync_with_stdio(false)
#define one first
#define two second
#define enld endl
#define neld endl
#define cosnt const
#define ppq priority_queue
#define rip return 0;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<pll, vector<pll>, greater<pll>> pq;

void yes() { cout << "YES" << endl; }
void no() { cout << "NO" << endl; }
void out1() { cout << outone << endl; }
void out2() { cout << outtwo << endl; }
ll max3 (ll a, ll b, ll c) { return max(a, max(b, c)); }
ll min3 (ll a, ll b, ll c) { return min(a, min(b, c)); }
ll ceill (ll a, ll b) { return (a+b-1)/b; }
long double flor(long double a){ return floor(a+0.5); }
ll logg (ll a, ll b) { return log(a)/log(b); }


const int maxn = 1000;
const int maxs = 2010;
int v[maxn];
int w[maxn];
int t[maxn];
ll dp[maxn][maxs];


int main(){
    migmig;
	int s, n;
	cin >> s >> n;
	for (int i=1; i<=n; i++){
		cin >> v[i] >> w[i] >> t[i];
	}
	if (n==1){
		cout << min(t[1], int(s/w[1]))*v[1] << endl;
		rip;
	}
	for (int i=1; i<=n; i++){
		for (int j=s; j>=0; j--){
			dp[i][j]=dp[i-1][j];
			for (int k=0; k<=t[i]; k++){
				if (j-(w[i]*k)>=0){
					dp[i][j]=max(dp[i][j], dp[i-1][j-w[i]*k]+v[i]*k);
				}
			}
			
		}
	}
	// for (int i=1; i<=n; i++){
		// for (int j=0; j<=s; j++){
			// cout << i << ", " <<j << ": " << dp[i][j] << endl;
		// }
	// }
	ll maxx = 0;
	for (int i=0; i<=s; i++){
		maxx = max(maxx, dp[n][i]);
	}
	cout << maxx << endl;
}

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