Submission #395201

#TimeUsernameProblemLanguageResultExecution timeMemory
395201ChrisTBulldozer (JOI17_bulldozer)C++17
75 / 100
1097 ms33472 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 2e3 + 5; #define lc ind<<1 #define rc ind<<1|1 struct Node { long long mn,mx; } tree[MN<<2]; void update (int ind, int tl, int tr, int i, long long v) { if (tl == tr) { tree[ind].mx += v; tree[ind].mn += v; return; } int mid = (tl + tr) / 2; if (i <= mid) update(lc,tl,mid,i,v); else update(rc,mid+1,tr,i,v); tree[ind].mn = min(tree[lc].mn,tree[rc].mn); tree[ind].mx = max(tree[lc].mx,tree[rc].mx); } long long queryMin (int ind, int tl, int tr, int l, int r) { if (tl > r || tr < l) return LLONG_MAX; if (l <= tl && tr <= r) return tree[ind].mn; int mid = (tl + tr) / 2; return min(queryMin(lc,tl,mid,l,r),queryMin(rc,mid+1,tr,l,r)); } long long queryMax (int ind, int tl, int tr, int l, int r) { if (tl > r || tr < l) return LLONG_MIN; if (l <= tl && tr <= r) return tree[ind].mx; int mid = (tl + tr) / 2; return max(queryMax(lc,tl,mid,l,r),queryMax(rc,mid+1,tr,l,r)); } int main () { int n,c=0; scanf ("%d",&n); vector<array<int,4>> pts(n); vector<int> pos(n), ow(n); vector<long long> vAt(n+1); for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w; vector<array<int,4>> events; for (int i = 0; i < n; i++) { for (int j = i+1; j < n; j++) { int dx = pts[i][0] - pts[j][0], dy = pts[i][1] - pts[j][1]; if (dx < 0) dx = -dx, dy = -dy; if (dx == 0 && dy < 0) dy = -dy; events.push_back({dx,dy,i,j}); } } sort(pts.begin(),pts.end()); sort(events.begin(),events.end(),[&](const auto &a, const auto &b) {return (long long)a[1] * b[0] > (long long)b[1] * a[0];}); long long ret = 0, pre = 0; for (int i = 0; i < n; i++) { pos[pts[i][3]] = i+1; ret = max(ret,(long long)pts[i][2]); pre += pts[i][2]; vAt[i+1] = pre; update(1,1,n,i+1,pre); } for (auto &[x,y,i,j] : events) { if (pos[i] > pos[j]) swap(i,j); ret = max(ret,vAt[pos[j]] - min(0LL,queryMin(1,1,n,1,pos[i]-1)) - min(0,ow[i]) - min(0,ow[j])); ret = max(ret,queryMax(1,1,n,pos[j],n) - (pos[i] == 1 ? 0LL : vAt[pos[i]-1]) - min(0,ow[i]) - min(0,ow[j])); update(1,1,n,pos[i],ow[j]-ow[i]); vAt[pos[i]] += ow[j] - ow[i]; swap(pos[i],pos[j]); } printf ("%lld\n",ret); return 0; }

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:33:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  int n,c=0; scanf ("%d",&n);
      |             ~~~~~~^~~~~~~~~
bulldozer.cpp:36:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w;
      |                               ~~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...