Submission #1169543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169543		shiomusubi496	Bulldozer (JOI17_bulldozer)	C++20	25 / 100	2080 ms	554920 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;

template<class M> class SegmentTree {
    using T = typename M::T;

    int n;
    vector<T> dat;

public:
    SegmentTree(vector<T> v) {
        n = 1;
        while (n < v.size()) n *= 2;
        dat.assign(2 * n, M::id());
        rep (i, v.size()) dat[i + n] = v[i];
        for (int i = n - 1; i >= 1; --i) dat[i] = M::op(dat[i * 2], dat[i * 2 + 1]);
    }
    void set(int k, T x) {
        k += n;
        dat[k] = x;
        while (k > 1) {
            k /= 2;
            dat[k] = M::op(dat[k * 2], dat[k * 2 + 1]);
        }
    }
    T all_prod() const { return dat[1]; }
};

struct Monoid {
    struct T {
        ll lmx, rmx, mx, sm;
    };
    static T id() { return {-inf, -inf, -inf, 0}; }
    static T op(T a, T b) {
        return {
            max(a.lmx, a.sm + b.lmx),
            max(a.rmx + b.sm, b.rmx),
            max({a.mx, b.mx, a.rmx + b.lmx}),
            a.sm + b.sm
        };
    }
    static T get(ll x) { return {max(0ll, x), max(0ll, x), max(0ll, x), x}; }
};

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(); }

    void debug() const { cerr << num << "/" << den << endl; }

    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]);
    if (N == 1) {
        printf("%lld\n", max(0ll, A[0][2]));
        return 0;
    }
    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;
    SegmentTree<Monoid> seg([&] {
        vector<typename Monoid::T> C(N);
        rep (i, N) C[i] = Monoid::get(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() - 1) assert(abs(Q[v[i]] - Q[v[i + 1]]) == 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], Monoid::get(A[a][2])); seg.set(Q[b], Monoid::get(A[b][2]));
            }
        }
        chmax(ans, seg.all_prod().mx);
        for (auto [xx, v] : mp2) {
            seen[xx] = false;
            for (auto i : v) seen[i] = false;
        }
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     int N; scanf("%d", &N);
      |            ~~~~~^~~~~~~~~~
bulldozer.cpp:87:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     rep (i, N) rep (j, 3) scanf("%lld", &A[i][j]);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~

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