제출 #474843

#제출 시각아이디문제언어결과실행 시간메모리
474843BackNoobKnapsack (NOI18_knapsack)C++14
100 / 100
73 ms7416 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define mask(i) (1LL << (i)) #define task "name" #define ull unsigned long long using namespace std; const ll mxN = 220797 + 7; const ll inf = 1e9 + 277; const ll mod = 2147483648; const ll infll = 1e18 + 7; const ll base = 307; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } struct item{ ll v , w , k; } a[mxN]; ll dp[3000]; vector<pair<ll , ll>> val[3000]; vector<ll> pre[3000]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //freopen("task.inp" , "r" , stdin); //freopen("task.out" , "w" , stdout); int s , n; cin >> s >> n; for(int i = 1 ; i <= n ; i++) cin >> a[i].v >> a[i].w >> a[i].k; for(int i = 1 ; i <= n ; i++) { val[a[i].w].push_back({a[i].v , a[i].k}); } for(int i = 1 ; i <= s ; i++) { sort(val[i].begin() , val[i].end() , greater<pair<ll,ll>>()); int cnt = 0; ll cur = 0; for(auto it : val[i]) { for(int j = 1 ; j <= it.se ; j++) { pre[i].push_back(cur + it.fi); cur += it.fi; ++cnt; if(cnt * i > s) break; } if(cnt * i > s) break; } } for(int i = 1 ; i <= s ; i++) for(int j = s ; j >= 0 ; j--) for(int idx = 0; idx < (int) pre[i].size() ; idx++) { if((idx + 1) * i > j) break; if(maximize(dp[j] , dp[j - (idx + 1) * i] + pre[i][idx]) == true && i == 15) { } } //for(int i = 1 ; i <= s ; i++) cout << dp[i] << endl; cout << dp[s] << endl; 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...