Submission #1210367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210367		Abito	Knapsack (NOI18_knapsack)	C++20	73 / 100	73 ms	32324 KiB

knapsack

#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=2e4+5,S=2005;
int n,s,f[S],dp[N][S],m;
vector<int> a[N];
pair<int,int> b[N];
bool cmp(vector<int> x,vector<int> y){
	if (x[1]!=y[1]) return x[1]>y[1];
	else return x[0]>y[0];
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>s>>n;
	for (int i=1;i<=s;i++) f[i]=s/i;
	for (int i=1;i<=n;i++){
		a[i].resize(3);
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	sort(a+1,a+1+n,cmp);
	for (int i=1;i<=n;i++){
		while (a[i][2] && f[a[i][1]]){
			m++;
			b[m]={a[i][0],a[i][1]};
			a[i][2]--;
			f[a[i][1]]--;
		}
	}
	swap(n,m);
	dp[0][0]=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=s;j++){
			dp[i][j]=dp[i-1][j];
			if (j-b[i].S>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-b[i].S]+b[i].F);
		}
	}
	int ans=0;
	for (int i=0;i<=s;i++) ans=max(ans,dp[n][i]);
	cout<<ans<<endl;
    return 0;
}

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