Submission #678995

#TimeUsernameProblemLanguageResultExecution timeMemory
678995lunchbox1Bulldozer (JOI17_bulldozer)C++17
100 / 100
728 ms63068 KiB
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
using namespace std;

#define ar array
#define ll long long

const int N = 2e3, N_ = 1 << 11;

ar<int, 2> norm(ar<int, 2> a) {
 int g = gcd(a[0], a[1]);
 a[0] /= g, a[1] /= g;
 if (a[1] < 0)
  a[0] *= -1, a[1] *= -1;
 return a;
}
bool comp(const ar<int, 2>& a, const ar<int, 2>& b) {
 return 1LL * a[0] * b[1] < 1LL * b[0] * a[1];
}

ar<ll, 4> operator+(const ar<ll, 4>& u, const ar<ll, 4>& v) {
 return {u[0] + v[0], max(u[1], u[0] + v[1]), max(v[2], u[2] + v[0]), max(u[2] + v[1], max(u[3], v[3]))};
}

int n_;
ar<ll, 4> t[N_ * 2];

void update(int i, int w) {
 t[i += n_] = {w, max(0, w), max(0, w), max(0, w)};
 while (i >>= 1)
  t[i] = t[i << 1 | 0] + t[i << 1 | 1];
}

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n;
 cin >> n;
 n_ = 1;
 while (n_ < n)
  n_ <<= 1;
 static ar<int, 3> p[N];
 for (int i = 0; i < n; i++) {
  auto &[x, y, w] = p[i];
  cin >> x >> y >> w;
 }
 sort(p, p + n);
 static pair<ar<int, 2>, ar<int, 2>> e[N * (N - 1) / 2];
 int m = 0;
 for (int i = 0; i < n; i++)
  for (int j = i + 1; j < n; j++)
   if (p[i][0] != p[j][0])
    e[m++] = make_pair(norm({p[j][1] - p[i][1], p[j][0] - p[i][0]}), ar<int, 2>{i, j});
 stable_sort(e, e + m, [&](const pair<ar<int, 2>, ar<int, 2>>& a, const pair<ar<int, 2>, ar<int, 2>>& b) {
  return comp(a.first, b.first);
 });
 static int o[N];
 for (int i = 0; i < n; i++) {
  update(i, p[i][2]);
  o[i] = i;
 }
 ll ans = t[1][3];
 for (int h = 0; h < m; h++) {
  auto [s, ij] = e[h];
  auto [i, j] = ij;
  swap(o[i], o[j]);
  update(o[i], p[i][2]), update(o[j], p[j][2]);
  if (h == m - 1 || s != e[h + 1].first)
   ans = max(ans, t[1][3]);
 }
 cout << ans << '\n';
 return 0;
}
#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...