Submission #1274595

#TimeUsernameProblemLanguageResultExecution timeMemory
1274595KluydQKnapsack (NOI18_knapsack)C++20
100 / 100
41 ms3012 KiB
#include <bits/stdc++.h> #define respagold ios_base::sync_with_stdio(0), cin.tie(0); #define int long long #define ll long long #define int2 __int128_t #define FOR( i, x, n, d ) for( int i = x; i <= n; i += d ) #define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d ) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) (int)(x.size()) #define pb push_back #define ins insert #define lb lower_bound #define ub upper_bound #define pii pair <int, int> using namespace std; const int N = 2e3 + 12; const int mod = 1e9 + 7; const ll inf = 2e18; int n, m, x, y, z, dp[N]; vector <pii> g[N]; void solve() { cin >> m >> n; FOR( i, 1, n, 1 ) { cin >> x >> y >> z; g[y].pb({x, z}); } FOR( we, 1, m, 1 ) { sort( all(g[we]) ); x = 0; reverse( all(g[we]) ); for( auto i : g[we] ) { while( i.S > 0 && x < m / we ) { x ++, i.S --; FORR( j, m, we, 1 ) dp[j] = max(dp[j], dp[j - we] + i.F); } } } int ans = 0; FOR( i, 1, m, 1 ) ans = max(ans, dp[i]); cout << ans << '\n'; } signed main() { respagold; int test = 1; if( !test ) cin >> test; while( test -- ) 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...