Submission #118172

#	Time	Username	Problem	Language	Result	Execution time	Memory
118172		IOrtroiii	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1247 ms	32480 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

const int N = 2020;

using ll = long long;

struct Point {
   int x, y, w;
   Point(int x = 0, int y = 0, int w = 0) : x(x), y(y), w(w) {}
   bool operator < (const Point &p) const {
      return x < p.x || (x == p.x && y < p.y);
   }
   Point operator - (const Point &p) const {
      return Point(x - p.x, y - p.y);
   }
   ll cross(const Point &p) const {
      return (ll) x * p.y - (ll) y * p.x;
   }
};

int n;
Point a[N];
int pos[N];

ll ccw(pair<int, int> u, pair<int, int> v) {
   Point p = a[u.second] - a[u.first];
   Point q = a[v.second] - a[v.first];
   return p.cross(q);
}

struct State {
   ll sum, pref, suf, val;
   State(int x = 0) {
      sum = (ll) x;
      pref = suf = val = (ll) max(x, 0);
   };
   friend State operator + (const State &l, const State &r) {
      State ans;
      ans.sum = l.sum + r.sum;
      ans.pref = max(l.pref, l.sum + r.pref);
      ans.suf = max(r.suf, r.sum + l.suf);
      ans.val = max({l.val, r.val, l.suf + r.pref});
      return ans;
   }
};

State t[N << 2];

#define mid ((l + r) >> 1)

void modify(int v, int l, int r, int pos, int val) {
   if (l == r) {
      t[v] = State(val);
      return;
   }
   if (pos <= mid) {
      modify(v << 1, l, mid, pos, val);
   } else {
      modify(v << 1 | 1, mid + 1, r, pos, val);
   }
   t[v] = t[v << 1] + t[v << 1 | 1];
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> n;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i].x >> a[i].y >> a[i].w;
   }
   sort(a + 1, a + n + 1);
   vector<pair<int, int>> vals;
   for (int i = 1; i <= n; ++i) {
      for (int j = i + 1; j <= n; ++j) {
         vals.emplace_back(i, j);
      }
   }
   sort(vals.begin(), vals.end(), [&](pair<int, int> u, pair<int, int> v) {
      ll cur = ccw(u, v);
      if (cur) {
         return cur < 0;
      } else {
         return u < v;
      }
   });
   for (int i = 1; i <= n; ++i) {
      pos[i] = i;
      modify(1, 1, n, i, a[i].w);
   }
   ll ans = t[1].val;
   for (int i = 0; i < (int) vals.size(); ++i) {
      vector<pair<int, int>> sw(1, vals[i]);
      while (i + 1 < (int) vals.size() && !ccw(vals[i], vals[i + 1])) {
         sw.emplace_back(vals[++i]);
      }
      for (auto p : sw) {
         int u, v;
         tie(u, v) = p;
         swap(pos[u], pos[v]);
         modify(1, 1, n, pos[u], a[u].w);
         modify(1, 1, n, pos[v], a[v].w);
      }
      ans = max(ans, t[1].val);
   }
   cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20