Submission #976756

#	Time	Username	Problem	Language	Result	Execution time	Memory
976756		vjudge1	Knapsack (NOI18_knapsack)	C++17	0 / 100	119 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pll pair<ll,ll>

const ll MOD=1e9+7;

// #define ll int
//KALAU TAKUT RTE

bool cmp (pair<ll,ll> x, pair<ll,ll>y){
	return x.second < y.second;
}

ll expo(ll x, ll y){
	if (y==0) return 1;
	ll ans = expo((x*x)%MOD, y/2);
	if (x%2) return (ans * x)%MOD;
	return ans%MOD;
}

vector<pll> vec[2007];
ll dp[2007][100007];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	ll s,n; cin>>s>>n;
	
	for (int i=1; i<=n;i++){
		ll a,b,c; cin>>a>>b>>c;
		vec[b].pb({a,c});
	}
	for (int i=1; i<=s; i++) sort(vec[i].begin(),vec[i].end(), greater<pll>());
	
	memset(dp, 0 ,sizeof(dp));
	for (int i=1 ;i<=s; i++){
		for (int j=1; j<=s; j++){
			dp[i][j]=dp[i-1][j];
			if (vec[i].size()==0) continue;
			ll cnt =0; ll cur=0;
			for (auto x : vec[i]){
				if (cnt > j) break;
				ll tmp = x.second;
				
				for (int k=0; k<x.second; k++){
					cnt += i;
					cur += x.first;
					if (cnt>j) break;
					dp[i][j] = max(dp[i][j], dp[i-1][j-cnt]+cur);
				}
			}
		}
	}
	cout<<dp[s][s]<<endl;
	
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:45:8: warning: unused variable 'tmp' [-Wunused-variable]
   45 |     ll tmp = x.second;
      |        ^~~

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