제출 #1084591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1084591		rxlfd314	Bulldozer (JOI17_bulldozer)	C++17	60 / 100	646 ms	33732 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#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(i, 0, N-1)
    FOR(j, 0, N-1)
      if (i != j && (X[i] > X[j] || X[i] == X[j] && Y[i] > Y[j]))
        sweep.push_back(Event(Y[i] - Y[j], X[i] - X[j], i, j));
  
  sort(all(sweep), [&](const Event &a, const Event &b) {
    ll va = 1ll * a.y * b.x;
    ll vb = 1ll * b.y * a.x;
    return va != vb ? va < vb : ari2{-X[a.i], -X[a.j]} < ari2{-X[b.i], -X[b.j]};
  });
  
  vt<int> ord(N);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return X[a] < X[b];    
  });
  
  vt<int> pos(N);
  FOR(ii, 0, N-1) {
    const int i = ord[ii];
    pos[i] = ii;
    st.update(ii, W[i]);
  }
  
  ll ans = st.query(0, N-1).ans;
  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);
  }
  
  cout << ans << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:68:50: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |       if (i != j && (X[i] > X[j] || X[i] == X[j] && Y[i] > Y[j]))
      |                                     ~~~~~~~~~~~~~^~~~~~~~~~~~~~

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