제출 #501376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501376		zhangjishen	Knapsack (NOI18_knapsack)	C++98	73 / 100	1088 ms	17124 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){
			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]);
}

컴파일 시 표준 에러 (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