Submission #501372

#	Time	Username	Problem	Language	Result	Execution time	Memory
501372		zhangjishen	Knapsack (NOI18_knapsack)	C++98	37 / 100	2 ms	460 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;

const int MAXN = 3e6 + 10, MAXS = 2e3 + 10;

int s, n;
ll v[MAXN], w[MAXN], f[MAXS];

int main(){
	// input
	scanf("%d %d", &s, &n);
	int a, b, c;
	int t = 0;
	for(int i = 1; i <= n; i++){
		scanf("%d %d %d", &a, &b, &c);
		for(int p = 1; p <= c; p *= 2){
			t++; c -= p;
			v[t] = p * a;
			w[t] = p * b;
		}
		if(c){
			t++; 
			v[t] = c * a;
			w[t] = c * b;
		}
	}
	n = t;
	// dp
	memset(f, 0, sizeof(f));
	for(int i = 1; i <= n; i++)
		for(int j = s; j >= 1; j--)
			if(w[i] <= j)
				chkmax(f[j], f[j - w[i]] + v[i]);
	printf("%lld\n", f[s]);
}

Compilation message (stderr)

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

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