제출 #782453

#제출 시각아이디문제언어결과실행 시간메모리
782453amukkalirKnapsack (NOI18_knapsack)C++17
0 / 100
88 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define ioss ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define int long long #define pii pair<int, int> #define fi first #define se second #define pb push_back int t, n; vector<pii> v[2004]; vector<pii> items; bool comp(pii a, pii b) { return (a.fi > b.fi); } int dp[50004][2004]; int ks(int idx, int weight) { if(idx == items.size()) return 0; if(weight <= 0) return 0; if(dp[idx][weight] != -1) return dp[idx][weight]; int ret = ks(idx+1, weight); if(weight-items[idx].se >= 0) ret = max(ret, ks(idx+1, weight-items[idx].se)+items[idx].fi); return dp[idx][weight] = ret; } signed main() { ioss; memset(dp, -1, sizeof(dp)); cin >> t >> n; for(int i = 1; i <= n; i++) { int l, e, k; cin >> l >> e >> k; v[e].pb({l, min(t/e, k)}); } for(int i = 1; i <= t; i++) sort(v[i].begin(), v[i].end(), comp); for(int i = 1; i <= t; i++) { int tmp = 0; for(auto [val, cnt] : v[i]) { for(int j = 1; j <= cnt; j++) { if(tmp+i <= t) items.pb({val, i}), tmp += i; else break; } } } int ans = ks(0, t); cout << ans << endl; } /* 2000 + 2000/2 + 2000/3 */

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

knapsack.cpp: In function 'long long int ks(long long int, long long int)':
knapsack.cpp:17:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(idx == items.size()) return 0;
      |        ~~~~^~~~~~~~~~~~~~~
#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...