Submission #1048873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048873		tamir1	Knapsack (NOI18_knapsack)	C++17	100 / 100	72 ms	5088 KiB

knapsack

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,S,i,j,l,res,dp[2005],s,w,k;
vector<ll> v[2001];
vector<pair<ll,ll>> t[2001];
bool cmp(pair<ll,ll> a,pair<ll,ll> b){
	return a.first>b.first;
}
int main(){
	cin >> S >> n;
	for(i=1;i<=n;i++){
		cin >> s >> w >> k;
		t[w].push_back({s,k});
	}
	for(i=1;i<=S;i++){
		sort(t[i].begin(),t[i].end(),cmp);
		ll mx=S/i;
		for(j=0;j<t[i].size();j++){
			s=t[i][j].first;
			k=t[i][j].second;
			if(mx<=k){
				for(l=1;l<=mx;l++) v[i].push_back(s);
				break;
			}
			else{
				for(l=1;l<=k;l++) v[i].push_back(s);
				mx-=k;
			}
		}
		for(j=1;j<v[i].size();j++) v[i][j]+=v[i][j-1];
	}
	for(i=1;i<=S;i++){
		for(l=S;l>=i;l--){
			for(j=0;j<v[i].size();j++){
				if(l-i*(j+1)<0) break;
				dp[l]=max(dp[l],dp[l-i*(j+1)]+v[i][j]);
			}
		}
	}
	for(i=0;i<=S;i++) res=max(res,dp[i]);
	cout << res;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:19:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for(j=0;j<t[i].size();j++){
      |           ~^~~~~~~~~~~~
knapsack.cpp:31:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(j=1;j<v[i].size();j++) v[i][j]+=v[i][j-1];
      |           ~^~~~~~~~~~~~
knapsack.cpp:35:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    for(j=0;j<v[i].size();j++){
      |            ~^~~~~~~~~~~~

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