Submission #738901

#	Time	Username	Problem	Language	Result	Execution time	Memory
738901		MODDI	Knapsack (NOI18_knapsack)	C++14	0 / 100	104 ms	262144 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[100100][2100];
int main(){
	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][used] = max(dp[i][used], dp[i-1][used]);
			for(int j = 1; j * arr[i].second + used <= s && j <= ima[i]; j++){
				dp[i][j*arr[i].second + used] = max(dp[i][j*arr[i].second+used], dp[i-1][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][i]);
		
	cout<<best<<endl;
	return 0;
}

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