Submission #1038904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038904		juicy	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	883 ms	35524 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e3 + 5;

int n;
int ptr[N];
array<int, 3> pt[N];
array<long long, 4> s[4 * N];

array<long long, 4> operator + (const array<long long, 4> &lt, const array<long long, 4> &rt) {
  return {max(lt[0], lt[2] + rt[0]), max(lt[1] + rt[2], rt[1]), lt[2] + rt[2], max({lt[3], rt[3], lt[1] + rt[0]})};
}

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {pt[l][2], pt[l][2], pt[l][2], max(0, pt[l][2])};
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  s[id] = s[id * 2] + s[id * 2 + 1];
}

void upd(int i, int x, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {x, x, x, max(0, x)};
    return; 
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, id * 2, l, md);
  } else {
    upd(i, x, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
} 

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 3; ++j) {
      cin >> pt[i][j];
    }
  }
  sort(pt + 1, pt + n + 1);
  bld();
  vector<array<int, 4>> events;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      events.push_back({pt[j][1] - pt[i][1], pt[j][0] - pt[i][0], i, j});
    }
  }
  sort(events.begin(), events.end(), [&](const auto &a, const auto &b) {
    if ((long long) a[0] * b[1] == (long long) a[1] * b[0]) {
      return tie(a[2], a[3]) < tie(b[2], b[3]);
    }
    return (long long) a[0] * b[1] < (long long) a[1] * b[0];
  });
  iota(ptr + 1, ptr + n + 1, 1);
  auto res = s[1][3];
  for (int i = 0; i < events.size(); ++i) {
    int a = events[i][2], b = events[i][3];
    int &x = ptr[a], &y = ptr[b];
    upd(x, pt[b][2]);
    upd(y, pt[a][2]);
    swap(x, y);
    if (i + 1 == events.size() || (long long) events[i][0] * events[i + 1][1] != (long long) events[i + 1][0] * events[i][1]) {
      res = max(res, s[1][3]);
    }
  }
  cout << res;
  return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for (int i = 0; i < events.size(); ++i) {
      |                   ~~^~~~~~~~~~~~~~~
bulldozer.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     if (i + 1 == events.size() || (long long) events[i][0] * events[i + 1][1] != (long long) events[i + 1][0] * events[i][1]) {
      |         ~~~~~~^~~~~~~~~~~~~~~~

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