Submission #1142941

#TimeUsernameProblemLanguageResultExecution timeMemory
1142941AmirMakaMKnapsack (NOI18_knapsack)C++20
100 / 100
36 ms4164 KiB
#include <bits/stdc++.h> using namespace std; #define ull unsigned long long #define ll long long #define ld long double #define pb push_back #define f first #define s second #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pii pair<int,int> #define pll pair<ll,ll> #define pld pair<ld,ld> #define pdd pair<double,double> #define mp make_pair #define AmirMakaM ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) // solve it const ull SEED = chrono::steady_clock::now().time_since_epoch().count(); mt19937_64 mrand(SEED); ull rnd(ull x = ~(0ull)) {return mrand() % x;} const ll MOD = 998244353; const ll INF = 1e16+20; const int inf = 1e9 + 7; const ll N = 1e5+5; const ll M = 2e3+1; const double pi = 2*acos(0.0); const int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1}; void solve() { int m, n; cin >> m >> n; int v[n+1], w[n+1], k[n+1]; for(int i=1; i<=n; i++) cin >> v[i] >> w[i] >> k[i]; vector<pll> g[m+1]; for(int i=1; i<=n; i++) { g[w[i]].pb({v[i],k[i]}); } ll dp[m+1] = {}; for(int i=1; i<=m; i++) { sort(all(g[i])); reverse(all(g[i])); ll cur = m/i; for(int j=0; j<sz(g[i]); j++) { for(int t=1; t<=min(cur,g[i][j].s); t++) { for(int f=m; f>=i; f--) { if(dp[f-i] != 0 || f == i) { dp[f] = max(dp[f],dp[f-i] + g[i][j].f); } } } cur -= g[i][j].s; } } ll ans = 0; for(int i=1; i<=m; i++) ans = max(ans,dp[i]); cout << ans << '\n'; } int main() { AmirMakaM; srand(SEED); //freopen("bulk.in", "r", stdin); //freopen("bulk.out", "w", stdout); int ttt = 1; //cin >> ttt; while(ttt--) { solve(); } 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...