Submission #1169537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169537		shiomusubi496	Bulldozer (JOI17_bulldozer)	C++20	In queue	0 ms	0 KiB

bulldozer

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;
using PLL = pair<ll, ll>;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }

constexpr ll inf = 1e18;

class SubstrMax {
    vector<ll> v;

public:
    SubstrMax(vector<ll> v_) : v(v_) {}
    void set(int k, ll x) {
        v[k] = x;
    }
    ll all_prod() const {
        ll ans = 0;
        rep (l, v.size()) {
            ll sm = 0;
            rep2 (r, l, v.size()) {
                sm += v[r];
                chmax(ans, sm);
            }
        }
        return ans;
    }
};

class Rational {
    ll num, den;

    void normalize() {
        ll g = gcd(abs(num), abs(den));
        num /= g; den /= g;
        if (den < 0) {
            num = -num;
            den = -den;
        }
        else if (den == 0 && num < 0) num = -num;
    }

public:
    Rational() : Rational(0) {}
    Rational(ll x) : Rational(x, 1) {}
    Rational(ll x, ll y) : num(x), den(y) { normalize(); }

    friend bool operator<(Rational a, Rational b) { return a.num * b.den < b.num * a.den; }
};

int main() {
    int N; scanf("%d", &N);
    vector<array<ll, 3>> A(N);
    rep (i, N) rep (j, 3) scanf("%lld", &A[i][j]);
    map<Rational, map<int, vector<int>>> mp;
    rep (i, N) rep (j, i) {
        ll dx = A[j][0] - A[i][0], dy = A[j][1] - A[i][1];
        Rational r(dy, dx);
        mp[r][i].push_back(j);
        mp[r][j].push_back(i);
    }
    vector<int> P(N), Q(N);
    iota(all(P), 0);
    sort(all(P), [&](int i, int j) { return A[i][0] != A[j][0] ? A[i][0] < A[j][0] : A[i][1] < A[j][1]; });
    rep (i, N) Q[P[i]] = i;
    vector<bool> seen(N, false);
    ll ans = 0;
    SubstrMax seg([&] {
        vector<ll> C(N);
        rep (i, N) C[i] = A[P[i]][2];
        return C;
    }());
    for (auto [_, mp2] : mp) {
        for (auto [xx, v] : mp2) {
            if (seen[xx]) continue;
            v.push_back(xx);
            for (auto i : v) seen[i] = true;
            sort(all(v), [&](int i, int j) { return A[i][0] != A[j][0] ? A[i][0] < A[j][0] : A[i][1] < A[j][1]; });
            rep (i, v.size() / 2) {
                int a = v[i], b = v[v.size() - 1 - i];
                swap(Q[a], Q[b]);
                P[Q[a]] = a; P[Q[b]] = b;
                seg.set(Q[a], A[a][2]); seg.set(Q[b], A[b][2]);
            }
        }
        chmax(ans, seg.all_prod());
        for (auto [xx, v] : mp2) {
            seen[xx] = false;
            for (auto i : v) seen[i] = false;
        }
    }
    printf("%lld\n", ans);
}