Submission #1153500

#TimeUsernameProblemLanguageResultExecution timeMemory
1153500MPGKnapsack (NOI18_knapsack)C++20
100 / 100
214 ms34496 KiB
//#pragma GCC optomize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("O3") //#pragma GCC target("avx2") //#pragma GCC target("sse,sse2,sse4.1,sse4.2") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define max_heap priority_queue<pair <ll, pair <ll, ll>>> #define min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> //#define min_heap priority_queue<ll, vector<ll>, greater<ll>> #define sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); #define filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout); #define endl '\n' #define md(a) (a % mod + mod) % mod #define pb push_back //cout << vectorprecision(5) << fixed << f; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn = 2e5 + 123; ll const inf = 2e18; ll const loG = 23; //ll const mod = 1e9 + 7; ll const mod = 998244353; ll const sq = 350; ll power(ll a, ll b, ll mod){if(b==0)return 1;if(b==1)return a;ll x = power(a, b / 2, mod);return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;} ll n, s, dp[2024][2024]; vector <pair <ll, ll>> vec[2025]; void Solve(){ cin >> s >> n; for (int i = 1; i < n + 1; i++){ ll a, b, c; cin >> a >> b >> c; vec[b].push_back({a, c}); } for (int i = 1; i < s + 1; i++){ sort(vec[i].begin(), vec[i].end()); reverse(vec[i].begin(), vec[i].end()); } for (int i = 1; i < s + 1; i++){ for (int j = 1; j < s + 1; j++){ dp[i][j] = dp[i - 1][j]; ll w = 0, pol = 0; for (auto p : vec[i]){ ll k = p.second; while (k){ k--; w += i; pol += p.first; if ((w > j)) break; dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + pol); } } } } ll ans = 0; for (int i = 0; i < s + 1; i++) ans = max(ans, dp[s][i]); cout << ans << endl; } int main(){ sariE;// filE; int test = 1; //cin >> test; while (test--) 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...