Submission #634113

#	Time	Username	Problem	Language	Result	Execution time	Memory
634113		omeganot	Knapsack (NOI18_knapsack)	C++14	100 / 100	104 ms	19680 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll mod = 1e9+7;
const int inf = 1e9; const ll infll = 1e18;

int s; int n;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	cin >> s >> n;
	vector<vector<pair<int,int>>> a(s+1);
	vector<vector<int>> b(s+1,{0});
	for(int i=0;i<n;i++) {
		int v; int w; int k;
		cin >> v >> w >> k;
		a[w].push_back({v,k});
	}
	for(int i=1;i<=s;i++) {
		sort(a[i].begin(),a[i].end(),greater<pair<int,int>>());
		int j = 0;
		while(j<a[i].size()&&b[i].size()<=s+1) {
			b[i].push_back(a[i][j].first+b[i].back());
			a[i][j].second--;
			if(!a[i][j].second) {
				j++;
			}
		} 
	}
	vector<ll> dp(s+1);
	vector<ll> dp2(s+1);
	for(int i=1;i<=s;i++) {
		for(int j=s;j>=0;j--) {
			dp2[j] = max(dp[j],dp2[j]);
			for(int k=1;k*i<=s&&k<b[i].size();k++) {
				if(j+i*k<=s) {
					dp2[j+i*k] = max(dp2[j+i*k],dp[j]+b[i][k]); 
				}
			}
		}
		swap(dp,dp2);
		fill(dp2.begin(),dp2.end(),0);
	}
	ll ans = 0;
	for(int i=1;i<=s;i++) {
		ans = max(ans,dp[i]);
	}
	cout << ans << "\n";
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   while(j<a[i].size()&&b[i].size()<=s+1) {
      |         ~^~~~~~~~~~~~
knapsack.cpp:25:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |   while(j<a[i].size()&&b[i].size()<=s+1) {
      |                        ~~~~~~~~~~~^~~~~
knapsack.cpp:38:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |    for(int k=1;k*i<=s&&k<b[i].size();k++) {
      |                        ~^~~~~~~~~~~~

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