Submission #738908

#	Time	Username	Problem	Language	Result	Execution time	Memory
738908		MODDI	Knapsack (NOI18_knapsack)	C++14	73 / 100	1079 ms	2896 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, s;
vector<pii> arr;
int ima[100100];
ll dp[2][2100];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>s>>n;
	for(int i = 0; i < n; i++){
		int a, b;
		cin>>a>>b>>ima[i];
		arr.pb(mp(a,b));
	}
	memset(dp, 0, sizeof dp);
	for(int j = 1; j * arr[0].second <= s && j <= ima[0]; j++){
		dp[0][j*arr[0].second] = j * arr[0].first;
	}
	for(int i = 1; i < n; i++){
		for(int used = 0; used <= s; used++){
			dp[i%2][used] = max(dp[i%2][used], dp[(i-1)%2][used]);
			for(int j = 1; j * arr[i].second + used <= s && j <= ima[i]; j++){
				dp[i%2][j*arr[i].second + used] = max(dp[i%2][j*arr[i].second+used], dp[(i-1)%2][used] + arr[i].first * j);
			}
		}
	}
//	for(int i = 0; i < n; i++){
//		for(int j = 0; j <= s; j++){
//			cout<<dp[i][j]<<" ";
//		}
//		cout<<endl;
//	}
	ll best = 0;
	for(int i = 0; i <= s; i++)
		best = max(best, dp[(n-1)%2][i]);
		
	cout<<best<<endl;
	return 0;
}

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