Submission #947934

#TimeUsernameProblemLanguageResultExecution timeMemory
947934ha819haBulldozer (JOI17_bulldozer)C++17
100 / 100
558 ms33568 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int,int>; using pll = pair<ll, ll>; #define x first #define y second #define all(v) (v).begin(), (v).end() const int SZ = 2048; struct Tree { long long L[SZ + SZ], R[SZ + SZ], S[SZ + SZ], M[SZ + SZ]; void Put(int a, int b) { a += SZ; S[a] = b; L[a] = R[a] = M[a] = max(0, b); while (a != 1) { a >>= 1; S[a] = S[a + a] + S[a + a + 1]; L[a] = max(L[a + a], S[a + a] + L[a + a + 1]); R[a] = max(R[a + a + 1], S[a + a + 1] + R[a + a]); M[a] = max(max(M[a + a], M[a + a + 1]), R[a + a] + L[a + a + 1]); } } }T; struct Point { int x,y,v; bool operator < (const Point& rhs) const { return pii(x, y) < pii(rhs.x, rhs.y); } }; struct Line { int x, y, i, j; bool operator<(const Line &p)const { return (long long)y*p.x != (long long)p.y*x ? (long long)y*p.x < (long long)p.y*x : i!=p.i?i<p.i:j<p.j; } }; int main(void){ cin.tie(0)->sync_with_stdio(0); int n; cin>>n; vector<Point> p(n); for(auto& [x,y,v]:p) cin>>x>>y>>v; sort(all(p)); vector<int> pos(n); vector<Line> lines; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { int dx = p[j].x-p[i].x; int dy = p[j].y-p[i].y; if (dx < 0 || (dx == 0 && dy < 0))dx = -dx, dy = -dy; lines.push_back({dx,dy,i,j}); } } sort(all(lines)); for(int i=0;i<n;i++) { T.Put(i, p[i].v); pos[i]=i; } ll ans = T.M[1]; int cnt = lines.size(); for (int i = 0,j; i < cnt; i++) { for (j = i; j < cnt; j++) { if ((long long)lines[i].x*lines[j].y != (long long)lines[i].y*lines[j].x)break; int a = lines[j].i, b = lines[j].j; swap(pos[a], pos[b]); T.Put(pos[a], p[a].v); T.Put(pos[b], p[b].v); } ans = max(ans, T.M[1]); i=j-1; } cout<<ans; }
#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...