Submission #799009

#TimeUsernameProblemLanguageResultExecution timeMemory
799009MadokaMagicaFanCatfish Farm (IOI22_fish)C++17
9 / 100
229 ms25760 KiB
#include "fish.h" #include "bits/stdc++.h" using namespace std; using ll = long long; #define sz(v) ((int) v.size()) const int N = 1e5; int dp1[N+5], dp2[N+5]; struct aint { int n; vector<ll> f; aint (int _n) { n = _n; f.assign(n<<1, 0); } ll query(int l, int r) { l += n; r += n+1; ll res = 0; for (;l < r; l>>=1, r>>=1) { if (l&1) res = max(res, f[l++]); if (r&1) res = max(res, f[--r]); } return res; } void upd(int x, ll v) { x += n; for (f[x] = max(f[x], v); x > 1; x>>=1) { f[x>>1] = max(f[x], f[x^1]); } } }; ll mv1[N+5], mv2[N+5]; ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) { vector<array<int, 3>> u(m), d(m); for (int i = 0; i < m; ++i) { u[i] = {x[i], y[i], i}; d[i] = {x[i], -y[i], i}; } sort(u.begin(), u.end()); sort(d.begin(), d.end()); reverse(u.begin(), u.end()); reverse(d.begin(), d.end()); int up, dp; up = dp = 0; aint t1(n+5), t2(n+5); ll t, v, i; for (int x = n-1; x >= 0; --x) { while (up < sz(u) && u[up][0] >= x) { if (x < n-1) { i = u[up][2]; v = w[i]; t = t1.query(y[i]+1, n+2); t = max(t, mv2[x+2]) + v; t1.upd(y[i], t); } ++up; } while (dp < sz(d) && d[dp][0] >= x) { if (x > 0) { i = d[dp][2]; v = w[i]; t = 0; if (y[i]) t = t2.query(0, y[i]-1); t = max(t, mv1[x+1]) + v; t2.upd(y[i], t); } ++dp; } mv1[x] = mv1[x+1]; mv2[x] = mv2[x+1]; mv1[x] = max(mv1[x], t1.query(0, n+1)); mv2[x] = max(mv2[x], t2.query(0, n+1)); } return max(t1.query(0, n+1), t2.query(0, n+1)); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...