제출 #1060459

#제출 시각아이디문제언어결과실행 시간메모리
1060459vjudge1Knapsack (NOI18_knapsack)C++17
100 / 100
46 ms3924 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define BIT(i) (1LL << (i)) #define GBIT(mask,i) (((mask) >> (i)) & 1) #define ALL(v) v.begin(),v.end() #define pb push_back #define sz(v) ((int)v.size()) #define FOR(i,a,b) for(int i = a; i <= b; ++i) #define FOD(i,a,b) for(int i = a; i >= b; --i) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int inf = 2e9 + 7; const long long infll = 1e18 + 7; template<class T1,class T2> bool maximize(T1 &a,T2 b) { if(a < b) { a = b; return 1; } return 0; } template<class T1,class T2> bool minimize(T1 &a,T2 b) { if(a > b) { a = b; return 1; } return 0; } #define MAX 2005 int s,n; vector<pii> adj[MAX]; ll dp[MAX]; void process() { cin >> s >> n; FOR(i,1,n) { int v,w,k; cin >> v >> w >> k; adj[w].pb({v,k}); } FOR(i,1,s) { if(sz(adj[i]) == 0) continue; sort(ALL(adj[i]),greater<pii>()); FOD(j,s,i) { int k = 0,cnt = 0,tmp = 0; ll sum = 0; while(k <= sz(adj[i]) && i * tmp <= j) { maximize(dp[j],dp[j - i * tmp] + sum); if(k == sz(adj[i])) break; cnt++; tmp++; sum += adj[i][k].fi; if(cnt == adj[i][k].se) { cnt = 0; k++; } } } } ll ans = 0; FOR(i,0,s) maximize(ans,dp[i]); cout << ans; } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define TASK "" if(fopen(TASK".inp","r")) { freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout); } if(fopen("main.inp","r")) { freopen("main.inp","r",stdin); freopen("main.out","w",stdout); } srand(time(0)); process(); cerr << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << "ms"; return 0; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(TASK".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(TASK".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen("main.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("main.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...