Submission #676477

#	Time	Username	Problem	Language	Result	Execution time	Memory
676477		penguin133	Knapsack (NOI18_knapsack)	C++17	100 / 100	455 ms	130776 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> >v[2005];
vector<pair<int ,int> >ans;
int n,s;
int dp[16005][2005];
int c(int i, int w){
	if(i >= ans.size())return 0;
	else if(dp[i][w] != -1)return dp[i][w];
	if(w >= ans[i].first)return dp[i][w] = max(c(i+1, w-ans[i].first) + ans[i].second, c(i+1, w));
	else return dp[i][w] = c(i+1, w);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> s >> n;
	for(int i=1;i<=n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		v[b].push_back(make_pair(a,c));
	}
	for(int i=1;i<=s;i++){
		sort(v[i].begin(), v[i].end(), greater<pair<int, int> >());
		int cnt = 0;
		for(int j=0;j<v[i].size();j++){
			if(cnt >= s/i)break;
			for(int k=0;k<min(s/i-cnt, v[i][j].second);k++)ans.push_back(make_pair(i, v[i][j].first));
			cnt = min(s/i, cnt + v[i][j].second);
		}
	}
	//for(int i=0;i<ans.size();i++)cout << ans[i].first << " " << ans[i].second << '\n';
	cout << c(0, s);
}

Compilation message (stderr)

knapsack.cpp: In function 'int c(int, int)':
knapsack.cpp:8:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  if(i >= ans.size())return 0;
      |     ~~^~~~~~~~~~~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int 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