제출 #395222

#제출 시각아이디문제언어결과실행 시간메모리
395222ChrisTBulldozer (JOI17_bulldozer)C++17
80 / 100
2091 ms81996 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<<1]; void update (int i, long long v) { i+=MN-1; for (tree[i].mn=tree[i].mx=v;i>1;i>>=1) { tree[i>>1].mn = min(tree[i].mn,tree[i^1].mn); tree[i>>1].mx = max(tree[i].mx,tree[i^1].mx); } } long long queryMin (int l, int r) { long long ret = LLONG_MAX; for (l += MN-1, r += MN; l < r; l >>= 1, r >>= 1) { if (l&1) ret = min(ret,tree[l++].mn); if (r&1) ret = min(ret,tree[--r].mn); } return ret; } long long queryMax (int l, int r) { long long ret = LLONG_MIN; for (l += MN-1, r += MN; l < r; l >>= 1, r >>= 1) { if (l&1) ret = max(ret,tree[l++].mx); if (r&1) ret = max(ret,tree[--r].mx); } return ret; } 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); vector<int> pAt(n+1); for (auto &[x,y,w,id] : pts) scanf ("%d %d %d",&x,&y,&w), id=c++, ow[id] = w; vector<tuple<int,int,long long,int,int>> 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,(long long)dx * pts[i][1] - (long long)dy * pts[i][0],i,j}); } } sort(pts.begin(),pts.end()); auto cmp = [&] (const auto &a, const auto &b) { long long getA = (long long)get<1>(a) * get<0>(b), getB = (long long)get<1>(b) * get<0>(a); return getA > getB || (getA == getB && get<2>(a) < get<2>(b)); }; sort(events.begin(),events.end(),[&](const auto &a, const auto &b) {return cmp(a,b);}); 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; pAt[i+1] = pts[i][3]; update(i+1,pre); } vector<vector<array<int,2>>> cur; auto solve = [&] () { for (auto &v : cur) { int mn = 1e9, mx = -1e9; for (auto &[i,j] : v) mn = min({mn,pos[i],pos[j]}), mx = max({mx,pos[i],pos[j]}); reverse(pAt.begin()+mn,pAt.begin()+mx+1); for (int i = mn; i <= mx; i++) { pos[pAt[i]] = i; vAt[i] = vAt[i-1] + ow[pAt[i]]; update(i,vAt[i]); } } for (auto &v : cur) { int mn = 1e9, mx = -1e9; for (auto &[i,j] : v) mn = min({mn,pos[i],pos[j]}), mx = max({mx,pos[i],pos[j]}); //go right long long get = queryMax(mx,n); for (int i = mx; i >= mn-1; i--) ret = max(ret,get - vAt[i]); //go left get = min(0LL,queryMin(1,mn-1)); for (int i = mn-1; i <= mx; i++) ret = max(ret,vAt[i] - get); //go middle? long long best = vAt[mn-1]; for (int i = mn; i <= mx; i++) { best = min(best,vAt[i]); ret = max(ret,vAt[i] - best); } } }; for (int idx = 0; idx < (int)events.size(); idx++) { if (idx > 0 && (long long)get<1>(events[idx]) * get<0>(events[idx-1]) != (long long)get<0>(events[idx]) * get<1>(events[idx-1])) { solve(); cur.clear(); } if (!cur.empty() && cmp(events[idx],events[idx-1]) == cmp(events[idx-1],events[idx])) cur.back().push_back({get<3>(events[idx]),get<4>(events[idx])}); else cur.push_back({{get<3>(events[idx]),get<4>(events[idx])}}); } if (!cur.empty()) solve(); printf ("%lld\n",ret); return 0; }

컴파일 시 표준 에러 (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...