Submission #1084578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084578		rxlfd314	Bulldozer (JOI17_bulldozer)	C++17	55 / 100	624 ms	33528 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 2005;
int N, X[mxN], Y[mxN], W[mxN];

struct Event {
  int y, x, i, j;
  Event(int _y, int _x, int _i, int _j) : y(_y), x(_x), i(_i), j(_j) {
    if (x < 0)
      y = -y, x = -x;
  }
};

struct Node {
  ll ans, lft, rht, sum;
  Node operator+(const Node &other) {
    return {
      max({ans, other.ans, rht + other.lft}),
      max(lft, sum + other.lft),
      max(other.rht, other.sum + rht),
      sum + other.sum
    };
  }
};

struct ST {
  Node st[mxN<<1];
  void update(int i, int v) {
    st[i+=N] = {max(v, 0), max(v, 0), max(v, 0), v};
    for (i >>= 1; i > 0; i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node lft = {0, 0, 0, 0};
    Node rht = {0, 0, 0, 0};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        lft = lft + st[l++];
      if (r & 1)
        rht = st[--r] + rht;
    }
    return lft + rht;
  }
} st;

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N;
  vt<Event> sweep;
  FOR(i, 0, N-1) {
    cin >> X[i] >> Y[i] >> W[i];
    FOR(j, 0, i-1)
      sweep.push_back(Event(Y[i] - Y[j], X[i] - X[j], j, i));
  }
  
  sort(all(sweep), [&](const Event &a, const Event &b) {
    return 1ll * a.y * b.x < 1ll * b.y * a.x;    
  });
  
  vt<int> ord(N);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return Y[a] - ll(1e9) * X[a] < Y[b] - ll(1e9) * X[b];    
  });
  
  vt<int> pos(N);
  FOR(ii, 0, N-1) {
    const int i = ord[ii];
    #ifdef DEBUG
    cout << i+1 << "\n "[ii+1<N];
    #endif
    pos[i] = ii;
    st.update(ii, W[i]);
  }
  
  ll ans = st.query(0, N-1).ans;
#ifdef DEBUG
  cout << ans << ':';
  sort(all(ord), [&](const int &a, const int &b) {
      return pos[a] < pos[b];    
      });
  for (int l : ord)
    cout << ' ' << l+1;
  cout << '\n';
#endif
  FOR(k, 0, size(sweep)-1) {
    auto [y, x, i, j] = sweep[k];
    st.update(pos[i], W[j]);
    st.update(pos[j], W[i]);
    swap(pos[i], pos[j]);
    if (k == size(sweep)-1 || 1ll * y * sweep[k+1].x != 1ll * sweep[k+1].y * x)
      ans = max(ans, st.query(0, N-1).ans);
#ifdef DEBUG
    cout << ans << ": (" << y << ' ' << x << ')';
    sort(all(ord), [&](const int &a, const int &b) {
        return pos[a] < pos[b];    
        });
    for (int l : ord)
      cout << ' ' << l+1;
    cout << '\n';
#endif
  }

  cout << ans << '\n';
}

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