제출 #537887

#제출 시각아이디문제언어결과실행 시간메모리
537887MrKusticBulldozer (JOI17_bulldozer)C++98
25 / 100
2085 ms188152 KiB
#include <bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define pb emplace_back #define x first #define y second using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int, int> pt; typedef pair<ll, ll> ptll; //typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //typedef gp_hash_table<int, int> table; void fastio(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); } //#pragma GCC optimize("Ofast") //------------------------------------------- struct Point { ll x, y, w; int id; bool top() const{ return (y > 0) || (y == 0 && x >= 0); }; ll distq(Point other = {0, 0}) const{ return (other.x - x) * (other.x - x) + (other.y - y) * (other.y - y); } ld dist(Point other = {0, 0}) const{ return sqrt(distq(other)); } void rev(){ x = -x, y = -y; } ll operator % (Point other) const{ return x * other.y - y * other.x; } ll operator * (Point other) const{ return x * other.x + y * other.y; } Point operator +(Point other) const{ return {x + other.x, y + other.y}; } Point operator -(Point other) const{ return {x - other.x, y - other.y}; } friend istream& operator >> (istream& in, Point &p){ in >> p.x >> p.y >> p.w; return in; } friend ostream& operator << (ostream& out, Point &p){ out << p.x << " " << p.y; return out; } }; struct Vector { ll x, y; int id1, id2; bool top() const{ return (y > 0) || (y == 0 && x >= 0); }; ll distq(Vector other = {0, 0}) const{ return (other.x - x) * (other.x - x) + (other.y - y) * (other.y - y); } ld dist(Vector other = {0, 0}) const{ return sqrt(distq(other)); } ld cock; void rev(){ x = -x, y = -y; } ll operator % (Vector other) const{ return x * other.y - y * other.x; } ll operator * (Vector other) const{ return x * other.x + y * other.y; } ll operator * (Point other) const{ return x * other.x + y * other.y; } Vector operator +(Vector other) const{ return {x + other.x, y + other.y}; } Vector operator -(Vector other) const{ return {x - other.x, y - other.y}; } friend istream& operator >> (istream& in, Vector &p){ in >> p.x >> p.y; return in; } friend ostream& operator << (ostream& out, Vector &p){ out << p.x << " " << p.y << " " << p.id1 << " " << p.id2 << " " << p.cock; return out; } }; const int MAXN = 2003; Point a[MAXN]; Vector vs[MAXN * MAXN]; int ids[MAXN]; int pos[MAXN]; ll pref[MAXN]; int n; ptll tree[2 * MAXN]; void upd(int i, ll val){ i += MAXN; for (tree[i] = ptll{val, val}; i > 1; i >>= 1){ tree[i >> 1].x = min(tree[i].x, tree[i ^ 1].x); tree[i >> 1].y = max(tree[i].y, tree[i ^ 1].y); } } ll getmin(int l, int r){ l += MAXN, r += MAXN; ll res = 1e18; while (l < r){ if (l & 1) res = min(res, tree[l++].x); if (r & 1) res = min(res, tree[--r].x); l >>= 1, r >>= 1; } return res; } ll getmax(int l, int r){ l += MAXN, r += MAXN; ll res = -1e18; while (l < r){ if (l & 1) res = max(res, tree[l++].y); if (r & 1) res = max(res, tree[--r].y); l >>= 1, r >>= 1; } return res; } pt upds[MAXN * 2]; ll calc(int ln){ ll res = 0; for (int j = 0; j < ln; j++){ for (int i = upds[j].x; i <= upds[j].y; i++){ ll mn = getmin(1, i + 1); ll mx = getmax(i + 1, n + 2); res = max(res, max(pref[i] - mn, mx - pref[i])); } } return res; } void run(){ cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; if (n == 1){ cout << max(0ll, a[0].w); return; } int m = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++){ if (i == j) continue; vs[m++] = {-(a[j] - a[i]).y, (a[j] - a[i]).x, i, j, (ld)(a[i] % a[j]) / (a[i].y != a[j].y ? a[i].y - a[j].y : (a[j].x - a[i].x))}; } } sort(vs, vs + m, [&](Vector p, Vector q){ bool ta = p.top(), tb = q.top(); if (ta != tb) return ta; ll cp = p % q; return (cp > 0 || (cp == 0 && p.cock < q.cock)); }); iota(ids, ids + n, 0); Vector start = {(int)2e9 + 110, -1}; sort(ids, ids + n, [&](int i, int j){ return start * a[i] < start * a[j]; }); for (int i = 1; i <= n; i++){ pref[i] = pref[i - 1] + a[ids[i - 1]].w; upd(i + 1, pref[i]); } for (int i = 0; i < n; i++) pos[ids[i]] = i; ll ans = 0; for (int i = 0; i < m; i++){ Vector curr = vs[i]; int j = i; int head; int t = 0; for (; j < m && curr % vs[j] == 0 && curr * vs[j] >= 0; j++){ head = j; for (; j + 1 < m && curr % vs[j + 1] == 0 && curr * vs[j + 1] >= 0 && abs(vs[head].cock - vs[j + 1].cock) < 1e-9; j++); int l = 1e9, r = -1; for (int k = head; k <= j; k++){ l = min(l, pos[vs[k].id1]); l = min(l, pos[vs[k].id2]); r = max(r, pos[vs[k].id1]); r = max(r, pos[vs[k].id2]); } for (int k = l; k <= (l + r) / 2; k++){ swap(ids[k], ids[r - k + l]); swap(pos[ids[k]], pos[ids[r - k + l]]); } for (int k = l; k <= r; k++){ pref[k + 1] = pref[k] + a[ids[k]].w; upd(k + 2, pref[k + 1]); } upds[t++] = {l + 1, r + 1}; } j--; ans = max(ans, calc(t)); i = j; } cout << ans; } int main(){ #ifdef LOCAL freopen("input.txt", "r", stdin); #else fastio(); //freopen("", "r", stdin); //freopen("", "w", stdout); #endif auto start = chrono::high_resolution_clock::now(); run(); auto stop = chrono::high_resolution_clock::now(); #ifdef LOCAL cerr << "Program finished in " << (ld)chrono::duration_cast<chrono::milliseconds>(stop - start).count() / 1e3 << " sec"; #endif return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:268:10: warning: variable 'start' set but not used [-Wunused-but-set-variable]
  268 |     auto start = chrono::high_resolution_clock::now();
      |          ^~~~~
bulldozer.cpp:270:10: warning: variable 'stop' set but not used [-Wunused-but-set-variable]
  270 |     auto stop = chrono::high_resolution_clock::now();
      |          ^~~~
#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...