Submission #265423

#TimeUsernameProblemLanguageResultExecution timeMemory
265423islingrBulldozer (JOI17_bulldozer)C++17
25 / 100
2087 ms154432 KiB
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 17;
using ll = int64_t;
const ll inf = 1e18;
struct S {
  ll pref, suff, ans, sum;
  S(ll x = 0) : sum{x} { ans = pref = suff = x > 0 ? x : 0; }
  S(const S &l, const S &r) : ans{max(l.ans, r.ans)} {
    pref = max(l.pref, l.sum + r.pref);
    suff = max(l.suff + r.sum, r.suff);
    ans = max(ans, l.suff + r.pref);
    sum = l.sum + r.sum;
  }
} t[N << 1];

int sz = 1;
void update(int p, ll x) { for (t[p += sz] = x; p >>= 1; ) t[p] = {t[p << 1], t[p << 1|1]}; }

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x...) begin(x), end(x)

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

using point = complex<ll>;
ll cross(const point &a, const point &b) { return imag(conj(a) * b); }
struct cmp {
  bool operator()(const point &a, const point &b) const { return cross(a, b) > 0; }
};

map<point, vector<pair<int, int>>, cmp> m;
int w[N], ord[N], pos[N];
point p[N];
vector<int> g[N], line;
bool vis[N];

void dfs(int u) {
  vis[u] = 1; line.push_back(u);
  for (int v : g[u]) if (!vis[v]) dfs(v);
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n; while (sz < n) sz <<= 1;
  rep(i, 0, n) { int x, y; cin >> x >> y >> w[i]; p[i] = {x, y}; ord[i] = i; }
  sort(ord, ord + n, [&](int a, int b) {
    return pair(imag(p[a]), -real(p[a])) < pair(imag(p[b]), -real(p[b]));
  });
  rep(i, 0, n) pos[ord[i]] = i;
  rep(i, 0, n) update(pos[i], w[i]);

  rep(i, 0, n) {
    rep(j, i + 1, n) {
      point z = p[i] - p[j];
      ll g = gcd(real(z), imag(z));
      z = {real(z) / g, imag(z) / g};
      if (imag(z) <= 0) z = -z;
      m[z].emplace_back(i, j);
      m[z].emplace_back(j, i);
    }
  }
  
  ll ans = t[1].ans;
  for (auto &[_, d] : m) {
    for (auto &[u, v] : d) g[u].push_back(v);
    for (auto &[_, v] : d) {
      if (vis[v]) continue;
      line.clear(); dfs(v);
      sort(all(line), [&](int x, int y) { return real(p[x]) < real(p[y]);});
      int s = line.size();
      for (int i = 0; i < s - i - 1; ++i)
        swap(pos[line[i]], pos[line[s - i - 1]]);
      for (int i : line) update(pos[i], w[i]);
    }

    for (auto &[_, v] : d) g[v].clear(), vis[v] = 0;
    ans = max(ans, t[1].ans);
  }

  cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...