Submission #1220209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220209		thinknoexit	Bulldozer (JOI17_bulldozer)	C++20	100 / 100	839 ms	50020 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 2020;
struct A {
    ll pref, suff, mx, sum;
    A operator + (const A& o) const {
        A t;
        t.pref = max(pref, sum + o.pref);
        t.suff = max(suff + o.sum, o.suff);
        t.mx = max({ mx, o.mx, suff + o.pref });
        t.sum = sum + o.sum;
        return t;
    }
} tree[4 * N];
int n;
void update(int v, ll w, int now = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[now] = { max(0ll, w), max(0ll, w), max(0ll, w), w };
        return;
    }
    int mid = (l + r) / 2;
    if (v <= mid) update(v, w, 2 * now, l, mid);
    else update(v, w, 2 * now + 1, mid + 1, r);
    tree[now] = tree[2 * now] + tree[2 * now + 1];
}
struct Fraction {
    ll x, y;
    Fraction(ll x, ll y) {
        if ((x * y < 0 && y < 0) || (x <= 0 && y < 0)) {
            x *= -1, y *= -1;
        }
        ll g = __gcd(abs(x), abs(y));
        this->x = x / g;
        this->y = y / g;
    }
    bool operator < (const Fraction& o) const {
        return y * o.x < o.y * x;
    }
    bool operator == (const Fraction& o) const {
        return y * o.x == o.y * x;
    }
};
ll x[N], y[N];
ll w[N];
int idx[N];
void sol1() {
    vector<int> v;
    for (int i = 1;i <= n;i++) v.push_back(i);
    sort(v.begin(), v.end(), [&](int a, int b) {
        if (x[a] != x[b]) return x[a] < x[b];
        return y[a] > y[b];
        });
    for (int i = 0;i < n;i++) {
        idx[v[i]] = i + 1;
        update(i + 1, w[v[i]]);
    }
}
void sol2() {
    vector<int> v;
    for (int i = 1;i <= n;i++) v.push_back(i);
    sort(v.begin(), v.end(), [&](int a, int b) {
        if (x[a] != x[b]) return x[a] < x[b];
        return y[a] < y[b];
        });
    for (int i = 0;i < n;i++) {
        idx[v[i]] = i + 1;
        update(i + 1, w[v[i]]);
    }
}
struct Intercept {
    Fraction x;
    int i, j;
    bool operator < (const Intercept& o) const {
        return x < o.x;
    }
};
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> x[i] >> y[i] >> w[i];
    sol2();
    ll ans = tree[1].mx;
    sol1();
    ans = max(ans, tree[1].mx);
    vector<Intercept> p;
    for (int i = 1;i <= n;i++) {
        for (int j = i + 1;j <= n;j++) {
            ll dy = y[j] - y[i];
            ll dx = x[j] - x[i];
            if (dx == 0) continue;
            p.push_back({ Fraction(dy, dx), i, j });
        }
    }
    sort(p.begin(), p.end());
    for (int i = 0, j;i < (int)p.size();i = j) {
        auto f = p[i].x;
        vector<pair<int, int>> v;
        for (j = i;j < (int)p.size() && p[i].x == p[j].x;j++) {
            v.push_back({ p[j].i, p[j].j });
        }
        // cout << f.x << ' ' << f.y << '\n';
        sort(v.begin(), v.end(), [&](pair<int, int> a, pair<int, int> b) {
            if (f.x * (x[a.first] - x[b.first]) != f.y * (y[a.first] - y[b.first]))
                return f.x * (x[a.first] - x[b.first]) < f.y * (y[a.first] - y[b.first]);
            if (min(idx[a.first], idx[a.second]) != min(idx[b.first], idx[b.second]))
                return min(idx[a.first], idx[a.second]) < min(idx[b.first], idx[b.second]);
            return max(idx[a.first], idx[a.second]) < max(idx[b.first], idx[b.second]);
            });
        for (auto& [a, b] : v) {
            update(idx[b], w[a]);
            update(idx[a], w[b]);
            swap(idx[a], idx[b]);
        }
        ans = max(ans, tree[1].mx);
    }
    cout << ans << '\n';
    return 0;
}

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