Submission #1095493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095493		Lollospadalaser	Knapsack (NOI18_knapsack)	C++17	100 / 100	448 ms	32848 KiB

knapsack

#ifdef LOCAL
#include "librerie locali/debugging.h"
#else
#pragma GCC optimize("Ofast,unroll-loops")
#endif
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x) for (int i = 0; i < (x); i++)
#define reps(i,j,x) for(int i=(j);i<(x);i++)
#define repp(i,x) for(int i = 1; i <= (x); i++)
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define maxint numeric_limits<int>::max()
#define minint numeric_limits<int>::min()
#define maxll numeric_limits<ll>::max()
#define minll numeric_limits<ll>::min()
#define nl '\n'
#define f first 
#define s second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef array<int, 3> i3;
typedef array<ll, 3> ll3;
typedef array<int, 4> i4;
typedef array<ll, 4> ll4;
typedef vector<i3> vi3;
typedef vector<ll3> vll3;
typedef vector<i4> vi4;
typedef vector<ll4> vll4;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
constexpr ll mod = 1000000007;
 
ll nxt() {ll x;cin >> x;return x;}
template <class T> void make_unique(T &arr) {sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());}
void print(){cout<<endl;} template <typename T, typename... Types> void print(T var1, Types... var2) {cout<<var1<<" ";print(var2...);}
template <typename T> T maxm(T var) {return var;} template <typename T, typename... Types> T maxm(T var1, Types... var2) {return max(var1,maxm(var2...));}
template <typename T> T minm(T var) {return var;} template <typename T, typename... Types> T minm(T var1, Types... var2) {return min(var1,minm(var2...));}
ll lpow(ll base, ll exp){ll result = 1;for (;;){if (exp & 1)result *= base;exp >>= 1;if (!exp)break;base *= base;}return result;}
int log2_floor(unsigned long long i) {return i ? __builtin_clzll(1) - __builtin_clzll(i) : 0;}
template <typename T> T maxv(vector<T> &var) {T maxi=numeric_limits<T>::min();for(auto x : var)maxi=max(maxi,x);return maxi;}
template <typename T> T minv(vector<T> &var) {T mini=numeric_limits<T>::max();for(auto x : var)mini=min(mini,x);return mini;}
ll fastExp(ll a, ll b){ll res = 1;while(b){if(b&1)res = res*a%mod;a = a*a%mod;b>>=1;}return res;}
ll modInv(ll a){return fastExp(a,mod-2);}
ll gcd(ll a, ll b,ll &x, ll &y){if(b == 0){x = 1;y = 0;return a;}ll x1,y1;ll g = gcd(b,a%b,x1,y1);x=y1;y=x1- y1 * (a/b);return g;}
ll gcd(ll a, ll b){if(b == 0)return a;return gcd(b,a%b);}

 
void solve();
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef LOCAL
	freopen("snakes.in", "r", stdin);
	#endif
	// freopen("snakes.out", "w", stdout);
	cout << fixed << setprecision(15);
	int t=1;
	// cin>>t;
	rep(i,t){
		solve();
	}
}

void solve(){
	int s,n;
	cin>>s>>n;
	vi curamount(s+1),dp(s+1);
	vector<vi3> object(s+1); // {val, weight, amount (compresi quelli precedenti)}
	rep(i,n){
		int v,w,amount;
		cin>>v>>w>>amount;
		if(w<=s)object[w].pb({v,w,amount});
	}
	rep(i,1+s)sort(allr(object[i]));
	repp(i,s)reps(j,1,object[i].size())object[i][j][2] += object[i][j-1][2];
	repp(i,s)if(object[i].size()){
		vector<vi3> newdp(s+1);
		rep(j,s+1)newdp[j].pb({dp[j],0,0});		//val, used, index in object
		reps(j,i,s+1){
			int best = 0;
			for(auto x : newdp[j-i]){
				if(x[1] == object[i][x[2]][2]){
					if(x[2] == object[i].size() - 1)break;
					x[2]++;
				}
				int cur = x[0] + object[i][x[2]][0];
				best = max(cur,best);
				newdp[j].pb({x[0] + object[i][x[2]][0], x[1] + 1, x[2]});
			}
			dp[j] = max(dp[j],best);
		}
	}
	cout<<dp[s]<<nl;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:9:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define reps(i,j,x) for(int i=(j);i<(x);i++)
      |                                    ^
knapsack.cpp:90:11: note: in expansion of macro 'reps'
   90 |  repp(i,s)reps(j,1,object[i].size())object[i][j][2] += object[i][j-1][2];
      |           ^~~~
knapsack.cpp:98:14: warning: comparison of integer expressions of different signedness: 'std::array<int, 3>::value_type' {aka 'int'} and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |      if(x[2] == object[i].size() - 1)break;

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