# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
901680 | 2024-01-09T23:24:57 Z | iliccmarko | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include <stdio.h> using namespace std; #define ll long long #define endl "\n" #define INF 1000000000 #define LINF 10000000000000000LL #define pb push_back #define all(x) x.begin(), x.end() #define len(s) (int)s.size() #define test_case { int t; cin>>t; while(t--)solve(); } #define single_case solve(); #define line cerr<<"----------"<<endl; #define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); } #define mod 1000000007LL long long max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) { vector<ll> val(n, 0); vector<set<ll> > visine(n); for (int i = 0; i < m; ++i) { visine[x[i]].insert(i); val[x[i]] += w[i]; } ll sigurno = 0; for (int i = 0; i < n; ++i) { ll cnt = 0; if (i - 1 >= 0) { for (ll ind : visine[i]) { if (y[ind] >= *visine[i - 1].begin()) break; cnt += (ll)w[ind]; } } if (i + 1 < n) { ll cnt1 = 0; for (ll ind : visine[i]) { if (y[ind] >= *visine[i + 1].begin()) break; cnt1 += (ll)w[ind]; } cnt = max(cnt, cnt1); } sigurno += cnt; val[i] -= (ll)cnt; } vector<vector<ll> > dp(n, vector<ll>(3, 0)); for (int i = 0; i < n; ++i) { if (i - 1 >= 0) { dp[i][0] = max({dp[i - 1][2], dp[i - 1][1], dp[i - 1][0]}); if (i + 1 < n) dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]); } if (i - 2 >= 0) { dp[i][1] = max(dp[i - 2][1] , dp[i - 2][2], dp[i - 2][0]); } if (i - 1 >= 0) dp[i][1] += (ll)val[i]; if (i + 1 < n) dp[i][2] += (ll)val[i]; } return max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) + sigurno; }