Submission #501389

#	Time	Username	Problem	Language	Result	Execution time	Memory
501389		zhangjishen	Knapsack (NOI18_knapsack)	C++98	100 / 100	97 ms	66444 KiB

knapsack

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

#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<int, int> pii;
const int MAXS = 2e3 + 10;

int n, s;
ll sum[MAXS][MAXS], f[MAXS][MAXS];
vector<pii> wei[MAXS];

bool cmp(pii a, pii b){
	return a.first > b.first;
}

int main(){
	scanf("%d %d", &s, &n);
	int v, w, k;
	for(int i = 1; i <= n; i++){
		scanf("%d %d %d", &v, &w, &k);
		wei[w].pb(mp(v, k));
	}
	for(int i = 1; i <= s; i++){
		sort(wei[i].begin(), wei[i].end(), cmp);
		int t = 1;
		for(int j = 0; j < (int)wei[i].size(); j++){
			v = wei[i][j].first, k = wei[i][j].second;
			for(int l = 1; l <= k && t <= s; l++, t++)
				sum[i][t] = sum[i][t - 1] + v;
		}
	}
	for(int i = 1; i <= s; i++)
		for(int j = 1; j <= s; j++)	
			for(k = 0; k <= j / i; k++)
				chkmax(f[i][j], f[i - 1][j - k * i] + sum[i][k]);
	printf("%lld\n", f[s][s]);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d %d", &s, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d %d %d", &v, &w, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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