제출 #976761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976761		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	53 ms	19540 KiB

knapsack

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

#define ll long long
#define pb push_back
#define pll pair<ll,ll>

const ll MOD=1e9+7;

#define ll int
//KALAU TAKUT RTE

bool cmp (pair<ll,ll> x, pair<ll,ll>y){
	return x.second < y.second;
}

ll expo(ll x, ll y){
	if (y==0) return 1;
	ll ans = expo((x*x)%MOD, y/2);
	if (x%2) return (ans * x)%MOD;
	return ans%MOD;
}


signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	ll s,n; cin>>s>>n;
	
	vector<pll> vec[s+1];
	ll dp[s+1][s+1];
	for (int i=1; i<=n;i++){
		ll a,b,c; cin>>a>>b>>c;
		vec[b].pb({a,c});
	}
	for (int i=1; i<=s; i++) sort(vec[i].begin(),vec[i].end(), greater<pll>());
	
	memset(dp, 0 ,sizeof(dp));
	for (int i=1 ;i<=s; i++){
		for (int j=1; j<=s; j++){
			dp[i][j]=dp[i-1][j];
			if (vec[i].size()==0) continue;
			ll cnt =0; ll cur=0;
			for (auto x : vec[i]){
				if (cnt > j) break;
				ll tmp = x.second;
				
				for (int k=0; k<x.second; k++){
					cnt += i;
					cur += x.first;
					if (cnt>j) break;
					dp[i][j] = max(dp[i][j], dp[i-1][j-cnt]+cur);
				}
			}
		}
	}
	cout<<dp[s][s]<<endl;
	
}

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

knapsack.cpp:10: warning: "ll" redefined
   10 | #define ll int
      | 
knapsack.cpp:4: note: this is the location of the previous definition
    4 | #define ll long long
      | 
knapsack.cpp: In function 'int main()':
knapsack.cpp:45:8: warning: unused variable 'tmp' [-Wunused-variable]
   45 |     ll tmp = x.second;
      |        ^~~

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