제출 #799031

#제출 시각아이디문제언어결과실행 시간메모리
799031MadokaMagicaFan메기 농장 (IOI22_fish)C++17
0 / 100
149 ms10304 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 (auto x : d) cout << x[0] << ' ' << -x[1] << endl; 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], mv1[x+3]}); t1.upd(y[i], t+v); } ++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], mv2[x+2]}) + v; t2.upd(y[i], t); } ++dp; } mv1[x] = mv1[x+1]; mv2[x] = mv2[x+1]; mv1[x] =t1.query(0, n+1); 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...