Submission #1218040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218040		Double_Slash	Bulldozer (JOI17_bulldozer)	C++20	75 / 100	506 ms	33612 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

struct Val {
    ll sum, lmx, rmx, mx;

    void operator=(int x) { lmx = rmx = mx = max(sum = x, 0ll); }

    Val operator+(const Val &o) const {
        Val ret{sum + o.sum, max(lmx, sum + o.lmx), max(rmx + o.sum, o.rmx)};
        ret.mx = max({mx, o.mx, ret.lmx, ret.rmx, rmx + o.lmx});
        return ret;
    }
};

struct St {
    int n;
    vector<Val> st;

    St(int n) : n(n), st(n << 1) {}

    void update(int i, int v) {
        for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    ll query(int l, int r) {
        Val lagg{}, ragg{};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lagg = lagg + st[l++];
            if (r & 1) ragg = st[--r] + ragg;
        }
        return (lagg + ragg).mx;
    }
};

pint operator-(const pint &a, const pint &b) { return {a.first - b.first, a.second - b.second}; }

ll operator^(const pint &a, const pint &b) { return (ll) a.first * b.second - (ll) b.first * a.second; }

int main() {
    int n;
    cin >> n;
    pint p[n];
    int w[n];
    for (int i = n; i--;) cin >> p[i].first >> p[i].second >> w[i];
    int arr[n];
    iota(arr, arr + n, 0);
    sort(arr, arr + n, [&] (int i, int j) { return p[i] < p[j]; });
    St st(n);
    int idx[n];
    for (int i = n; i--;) st.update(idx[arr[i]] = i, w[arr[i]]);
    vector<pair<pint, pint>> swaps;
    for (int i = n; i--;) {
        for (int j = n; j--;) {
            pint v = p[i] - p[j];
            if (v > pint{0, 0}) swaps.emplace_back(v, pint{i, j});
        }
    }
    sort(all(swaps), [&] (auto &a, auto &b) { return (a.first ^ b.first) < 0; });
    ll ans = st.query(0, n);
    for (int i = 0; i < swaps.size(); ++i) {
        auto [a, b] = swaps[i].second;
        if (idx[a] > idx[b]) {
            swap(idx[a], idx[b]);
            st.update(idx[a], w[a]);
            st.update(idx[b], w[b]);
        }
        if (i + 1 == swaps.size() or (swaps[i].first ^ swaps[i + 1].first)) ans = max(ans, st.query(0, n));
    }
    cout << ans;
}

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