Submission #501382

#	Time	Username	Problem	Language	Result	Execution time	Memory
501382		zhangjishen	Knapsack (NOI18_knapsack)	C++98	73 / 100	1084 ms	16136 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;

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

int main(){
	// input
	scanf("%lld %lld", &s, &n);
	ll a, b, c;
	ll t = 0;
	for(int i = 1; i <= n; i++){
		scanf("%lld %lld %lld", &a, &b, &c);
		for(ll p = 1; p <= c; p *= 2){
			if(p * b <= s){
				t++;
				v[t] = p * a;
				w[t] = p * b;
			}
			c -= p;
		}
		if(c && c * b <= s){
			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:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%lld %lld", &s, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   scanf("%lld %lld %lld", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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