Submission #673105

#	Time	Username	Problem	Language	Result	Execution time	Memory
673105		peijar	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	3 ms	708 KiB

bulldozer

#include <bits/stdc++.h>
#define int long long
using namespace std;

template <typename T> struct Point {
  T x, y;

  Point() : x(0), y(0) {}

  Point(T _x, T _y) : x(_x), y(_y) {}

  Point operator+(const Point other) const {
    return Point(x + other.x, y + other.y);
  }

  Point operator-(const Point other) const {
    return Point(x - other.x, y - other.y);
  }

  Point operator*(const T lambda) const {
    return Point(x * lambda, y * lambda);
  }

  Point operator/(const T lambda) const {
    return Point(x / lambda, y / lambda);
  }

  bool operator<(const Point &other) const {
    return tie(x, y) < tie(other.x, other.y);
  }
  bool operator==(const Point &other) const {
    return tie(x, y) == tie(other.x, other.y);
  }
  bool operator>(const Point &other) const { return other < *this; }
  bool operator!=(const Point &other) const { return !(*this == other); }
  bool operator<=(const Point &other) const { return !(other < *this); }
  bool operator>=(const Point &other) const { return other <= *this; }

  friend ostream &operator<<(ostream &out, const Point &a) {
    return out << a.x << " " << a.y;
  }
  friend istream &operator>>(istream &in, Point &a) { return in >> a.x >> a.y; }
  friend T dot(const Point a, const Point b) { return a.x * b.x + a.y * b.y; }

  friend T cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; }

  friend T dis2(const Point a, const Point b) { return dot(b - a, b - a); }
};

using P = Point<int>;

struct Angle {
  int x, y;

  Angle() : x(0), y(0) {}
  Angle(int _x, int _y) : x(_x), y(_y) {}

  int half() const {
    assert(x or y);
    return y < 0 or (!y and x < 0);
  }

  friend bool operator<(Angle a, Angle b) {
    return make_pair(a.half(), a.y * b.x) < make_pair(b.half(), a.x * b.y);
  }

  friend bool operator==(Angle a, Angle b) { return !(a < b) and !(b < a); }
};

const int MAXN = 1e4;

int iDeb[MAXN], iFin[MAXN];
int prefMax[MAXN], suffMax[MAXN], rangeSum[MAXN], maxSum[MAXN];

void pull(int node) {
  prefMax[node] =
      max(prefMax[2 * node], rangeSum[2 * node] + prefMax[2 * node + 1]);
  suffMax[node] =
      max(suffMax[2 * node + 1], rangeSum[2 * node + 1] + suffMax[2 * node]);
  maxSum[node] = max({maxSum[2 * node], maxSum[2 * node + 1],
                      suffMax[2 * node] + prefMax[2 * node + 1]});
  rangeSum[node] = rangeSum[2 * node] + rangeSum[2 * node + 1];
}

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  if (l == r)
    return;
  int m = (l + r) / 2;
  build(2 * node, l, m);
  build(2 * node + 1, m + 1, r);
}

void upd(int node, int pos, int x) {
  if (iDeb[node] > pos or iFin[node] < pos)
    return;
  if (iDeb[node] == iFin[node]) {
    rangeSum[node] = x;
    prefMax[node] = suffMax[node] = maxSum[node] = max(0LL, x);
    return;
  }

  upd(2 * node, pos, x);
  upd(2 * node + 1, pos, x);
  pull(node);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbPoints;
  cin >> nbPoints;
  vector<P> points(nbPoints);
  vector<int> poids(nbPoints);
  for (int i = 0; i < nbPoints; ++i)
    cin >> points[i] >> poids[i];
  vector<Angle> angles;
  for (int i = 0; i < nbPoints; ++i)
    for (int j = i + 1; j < nbPoints; ++j) {
      P diff = points[j] - points[i];
      angles.emplace_back(diff.x, diff.y);
      assert(diff.x or diff.y);
    }
  sort(angles.begin(), angles.end());
  angles.resize(unique(angles.begin(), angles.end()) - angles.begin());

  vector<int> ordreInit(nbPoints);
  iota(ordreInit.begin(), ordreInit.end(), 0LL);
  build(1, 0, nbPoints - 1);

  // On regarde ordre par rapport à OX

  auto getComparator = [&](P dir) {
    return [&points, dir](int i, int j) {
      if (cross(dir, points[i]) != cross(dir, points[j]))
        return cross(dir, points[i]) < cross(dir, points[j]);
      if (cross(dir, points[i]) > 0)
        return dot(dir, points[i]) < dot(dir, points[j]);
      return dot(dir, points[i]) > dot(dir, points[j]);
    };
  };

  sort(ordreInit.begin(), ordreInit.end(), getComparator({1, 0}));
  /*for (int i : ordreInit)
    cout << i << ' ';
  cout << endl;*/
  for (int i = 0; i < nbPoints; ++i)
    upd(1, i, poids[ordreInit[i]]);
  // cout << maxSum[1] << endl;
  int sol = maxSum[1];

  int nbAngles = angles.size();
  vector<vector<int>> withAngle(nbAngles);
  for (int i = 0; i < nbPoints; ++i)
    for (int j = i + 1; j < nbPoints; ++j) {
      P diff = points[j] - points[i];
      Angle a(diff.x, diff.y);
      int id = lower_bound(angles.begin(), angles.end(), a) - angles.begin();
      withAngle[id].push_back(i);
      withAngle[id].push_back(j);
    }
  vector<int> curPos(nbPoints);
  for (int i = 0; i < nbPoints; ++i)
    curPos[ordreInit[i]] = i;
  for (int i = 0; i < nbAngles; ++i)
    sort(withAngle[i].begin(), withAngle[i].end());
  for (int iAngle = 0; iAngle < nbAngles; ++iAngle) {
    Angle angle = angles[iAngle];
    Point dir(angle.x, angle.y);
    vector<int> toSort = withAngle[iAngle];
    sort(toSort.begin(), toSort.end());
    toSort.resize(unique(toSort.begin(), toSort.end()) - toSort.begin());
    sort(toSort.begin(), toSort.end(), getComparator(dir));
    vector<int> pos;
    for (int i : toSort)
      pos.push_back(curPos[i]);
    for (int i = 0; i < (int)toSort.size(); ++i) {
      upd(1, pos[i], poids[toSort[i]]);
      curPos[toSort[i]] = pos[i];
      ordreInit[pos[i]] = toSort[i];
    }
    /*cout << "-----------------\n";
    cout << dir << endl;
    for (int x : toSort)
      cout << x << ' ';
    cout << endl;*/
    sol = max(sol, maxSum[1]);
    /*for (int i : ordreInit)
      cout << i << ' ';
    cout << endl;
    cout << maxSum[1] << endl;*/
  }
  cout << sol << endl;
}

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