Submission #1265801

#TimeUsernameProblemLanguageResultExecution timeMemory
1265801nanaseyuzukiKnapsack (NOI18_knapsack)C++20
0 / 100
1 ms836 KiB
#include <bits/stdc++.h> /* --> Author: Kazuki_Hoshino__8703 <-- I love Nanasaki Ai ☆*: .。. o(≒_≒)o .。.:☆ */ #define fi first #define se second #define pii pair<int, int> #define int long long using namespace std; const int mn = 1e4 + 5, bm = (1 << 20) + 1; const int mod = 1e9 + 7, base = 31, inf = 1e9; int n, m, w[mn], v[mn], a[mn]; vector <pii> adj[mn]; vector <int> val[mn]; int dp[mn], tmp[mn]; void solve(){ cin >> n >> m; int max_val = 0; for(int i = 1; i <= n; i++){ cin >> a[i] >> w[i] >> v[i]; adj[w[i]].push_back({v[i], a[i]}); max_val = max(w[i], max_val); } // cerr << "ok\n"; for(int i = 1; i <= max_val; i++){ if(adj[i].empty()) continue; sort(adj[i].begin(), adj[i].end()); int num = 0, cur = 0; bool ok = true; val[i].push_back(0); while(!adj[i].empty() && ok){ int sl = adj[i].back().se; int gia = adj[i].back().fi; adj[i].pop_back(); for(int x = 1; x <= sl; x++){ num ++; cur += gia; val[i].push_back(cur); if(num == m / i){ ok = false; break; } } } } // cerr << "ok\n"; for(int i = 1; i <= max_val; i++){ if(val[i].size() <= 1) continue; for(int j = 1; j <= m; j++){ tmp[j] = dp[j]; } for(int j = val[i].size() - 1; j >= 1; j--){ int kl = i * j; int gia = val[i][j]; for(int ii = kl; ii <= m; ii++){ tmp[ii] = max(tmp[ii], dp[ii - kl] + gia); } } for(int j = 1; j <= m; j++){ dp[j] = tmp[j]; } } // cerr << "ok\n"; int res = 0; for(int i = 1; i <= m; i++){ res = max(res, dp[i]); } cout << res; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; while(t --){ solve(); } }
#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...