제출 #755346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755346		SriniV	Knapsack (NOI18_knapsack)	C++14	49 / 100	103 ms	262144 KiB

knapsack

/*
	Date: 09.06.2023
	Time:
	Learnt:
	Rating:
*/
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define PI 3.14159265358979323846
#define bits(x) __builtin_popcount(x)
#define pb push_back
#define trav(name , ds) for(auto&name : ds)
#define f first
#define s second
#define clr(ds) ds.clear()
#define all(ds) ds.begin() , ds.end()
#define pi pair<int , int>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define rsz(ds ,size , val) ds.assign(size , val);
using namespace std;

size_t hF(pair<int , int> a){
	return (a.first + a.second)*(a.first + a.second + 1)/2 + a.second;
}
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (name.size()) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}
ll s , n;
vll gain , cost;
void solve(){
	cin >> s >> n;
	for(int i =0;i<n;i++){
			ll v , w , k;
			cin >> v >> w >> k;
			k = min(k , (ll)ceil(s/(ld)w));
			for(int j= 0;j<k;j++)
				{
						gain.pb(v);
						cost.pb(w);
				}
	}
	n = gain.size();
	vector<vll> dp(n+1 , vll(s+1 , 0));//dp[i][j] -> Maximum value with cost j using first i elements

	for(int i = 0;i<n;i++){
			if(i==0){
						if(cost[i] <= s)
							dp[0][cost[i]] = gain[0];
						continue;
				}

			for(int j = 1;j<=s;j++){
					dp[i][j] = dp[i-1][j];
				if(cost[i] <= j ){
							dp[i][j] = max(dp[i][j] , dp[i-1][j-cost[i]] + gain[i]);
					}
			}
	}
	ll ans = 0;
	for(int i = 0 ;i<=s;i++)
		ans = max(ans , dp[n-1][i]);
	cout << ans << "\n";
}
int main(){
	setIO();
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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