제출 #1198502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198502		Zero_OP	Bulldozer (JOI17_bulldozer)	C++20	100 / 100	756 ms	33680 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x) "[" #x " = " << (x) << "]"

struct point{
      int x, y, c;
      bool operator < (const point& o) const {
            return make_pair(y, x) < make_pair(o.y, o.x);
      }
};

struct Node{
      ll pref, suff, best, sum;
      Node(ll s) : pref(s), suff(s), best(s), sum(s) {}
      Node(ll a, ll b, ll c, ll d) : pref(a), suff(b), best(c), sum(d) {}

      friend Node operator + (const Node& a, const Node& b){
            return Node(max(a.pref, a.sum + b.pref), max(b.suff, b.sum + a.suff), max({a.best, b.best, a.suff + b.pref}), a.sum + b.sum);
      }
};

struct SegmentTree{
      vector<Node> st;
      SegmentTree(int n) : st(n * 4, Node(0)) {}

      void update(int id, int l, int r, int pos, int val){
            if(l == r) st[id] = Node(val);
            else{
                  int mid = l + r >> 1;
                  if(pos <= mid) update(id << 1, l, mid, pos, val);
                  else update(id << 1 | 1, mid + 1, r, pos, val);
                  st[id] = st[id << 1] + st[id << 1 | 1];
            }
      }

      ll query(){
            return st[1].best;
      }
};

int sign(int x){
      return (x < 0 ? -1 : (x > 0 ? +1 : 0));
}

bool cmp(int a1, int b1, int a2, int b2){
      //vector u(a1, b1) and v(a2, b2)
//      int s1 = sign(a1), s2 = sign(a2);
//      if(s1 != s2) return s1 < s2;
//      return (s1 == +1 ? 1LL * a1 * b2 < 1LL * a2 * b1 : 1LL * a1 * b2 > 1LL * a2 * b1);
      return 1LL * a1 * b2 < 1LL * a2 * b1;
}

struct line{
      int x, y, l, r;
      line(int x, int y, int l, int r) : x(x), y(y), l(l), r(r) {}

      bool operator < (const line& o) const {
            if(x == o.x && y == o.y) return make_pair(l, r) < make_pair(o.l, o.r);
            return cmp(x, y, o.x, o.y);
      }
};

int main(){
      ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL

      int N;
      cin >> N;
      vector<point> p(N);
      for(int i = 0; i < N; ++i) cin >> p[i].x >> p[i].y >> p[i].c;

      sort(p.begin(), p.end());

      SegmentTree T(N);
      for(int i = 0; i < N; ++i) T.update(1, 0, N-1, i, p[i].c);
      ll ans = max(0ll, T.query());

      vector<line> v;
      for(int i = 0; i < N; ++i){
            for(int j = i+1; j < N; ++j){
                  ll a = p[i].x - p[j].x;
                  ll b = p[i].y - p[j].y;
                  ll d = __gcd(abs(a), abs(b));
                  a /= d; b /= d;
                  if(abs(a) == 1 && b == 0) continue;

                  if(b < 0) a = -a, b = -b;
                  v.emplace_back(line(a, b, i, j));
            }
      }

      sort(v.begin(), v.end());

      vector<int> idx(N);
      iota(idx.begin(), idx.end(), 0);

      auto output_idx = [&](){
            vector<int> pos(N);
            for(int i = 0; i < N; ++i) pos[idx[i]] = i;
            for(int i = 0; i < N; ++i) cout << p[pos[i]].c << ' '; cout << '\n';
//            for(int i = 0; i < N; ++i) cout << st<< ' '; cout << '\n';
            cout << "Checking \n\n";
      };


//      output_idx();
//      for(int i = 0; i < (int)v.size(); ++i) cout << '(' << v[i].x << ' ' << v[i].y << ") : " << v[i].l << ' ' << v[i].r << '\n';
//      cout << dbg(ans) << '\n';
//      return 0;
      for(int i = 0; i < (int)v.size(); ++i){
            int a = v[i].l, b = v[i].r;
            swap(idx[a], idx[b]);
            T.update(1, 0, N-1, idx[a], p[a].c);
            T.update(1, 0, N-1, idx[b], p[b].c);
//            cout << dbg(idx[a]) << dbg(idx[b]) << '\n';
            while(i+1 < (int)v.size() && v[i].x == v[i+1].x && v[i].y == v[i+1].y){
                  ++i;
                  int a = v[i].l, b = v[i].r;
                  swap(idx[a], idx[b]);
                  T.update(1, 0, N-1, idx[a], p[a].c);
                  T.update(1, 0, N-1, idx[b], p[b].c);
//                  cout << dbg(idx[a]) << dbg(idx[b]) << "!!\n";
            }

//            cout << dbg(ans) << '\n';
            ans = max(ans, T.query());
//            output_idx();
      }
      cout << ans << '\n';

      return 0;
}

/*

a, b, c -> c, b, a

(a, b), (a, c), (b, c)
a, b, c -> b, a, c -> b, c, a -> b, c, a

a, b, c, d, -> d, c, b, a
(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)

a, b, c, d
b, a, c, d
b, c, a, d
b, c, d, a
c, b, d, a


*/

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