Submission #928417

#	Time	Username	Problem	Language	Result	Execution time	Memory
928417		Nurislam	Knapsack (NOI18_knapsack)	C++14	73 / 100	1043 ms	1120 KiB

knapsack

#include <bits/stdc++.h>
//~ #include <ext/pb_ds/assoc_container.hpp> 
//~ #include <ext/pb_ds/tree_policy.hpp> 


using namespace std;
//~ using namespace __gnu_pbds; 
  

#define pb push_back
#define ff first
#define ss second
#define int long long
//~ #define double long double 
//~ #define order_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
///*                                                    __                    __                        __                    */
///*        ======     _      /| /|  __   _            /   |  |   /|  |   @  |    |  |  | /   /| |\  | /   |  |  @ | /        */
///* \-       ||  |_| |_     / |/ | |  | |_  |-        |   |--|  /-|  |   |  \ \  |==|  |-   /=| | \ | |   |--|  | |-         */
///*          ||  | | |_    /     | |__|  _| |_        \__ |  | /  |  |__ |  __|  |  |  | \ /  | |  \| \__ |  |  | | \        */
///* 

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;

const int N = 2e5+100, inf = 1e9, mod = 1e9+7;

void solve(){
	int s, n;
	cin >> s >> n;
	int dp[s+2]{};
	int ans = 0;
	for(int u = 0; u < n; u++){
		int sum, w, k;
		cin >> sum >> w >> k;
		k = min(k, s);
		while(k--){
			for(int i = s-w; i >= 0; i--){
				if(dp[i] > 0){
					dp[i+w] = max(dp[i+w], dp[i]+sum);
					ans = max(ans, dp[i+w]);
				}
			}dp[w] = max(dp[w], sum);
			ans = max(ans, dp[w]);
		}
	}
	//~ for(int i = 0; i <= s; i++)cout << dp[i] << ' ';
	//~ cout << '\n';
	cout << ans << '\n';
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int test = 1;
	//~ cin >> test;
	while(test--){
		solve();
	}
}

Compilation message (stderr)

knapsack.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main(){
      | ^~~~

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