Submission #401918

#	Time	Username	Problem	Language	Result	Execution time	Memory
401918		timmyfeng	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	976 ms	50124 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

using point = complex<long long>;
#define X real()
#define Y imag()

const int N = 2000;

struct segtree {
    segtree *left = nullptr, *right = nullptr;
    long long prefix = 0, suffix = 0, sum = 0, maxi = 0;

    void update(int a, int x, int l, int r) {
        if (l == r) {
            prefix = suffix = maxi = max(0, x);
            sum = x;
        } else {
            if (!left) {
                left = new segtree();
                right = new segtree();
            }

            int m = (l + r) / 2;
            if (a <= m) {
                left->update(a, x, l, m);
            } else {
                right->update(a, x, m + 1, r);
            }

            prefix = max(left->prefix, left->sum + right->prefix);
            suffix = max(left->suffix + right->sum, right->suffix);
            sum = left->sum + right->sum;
            maxi = max({left->maxi, right->maxi, left->suffix + right->prefix});
        }
    }
};

long long cross(point a, point b) {
    return a.X * b.Y - a.Y * b.X;
}

bool comp(point a, point b) {
    if (a.X == b.X) {
        return a.Y < b.Y;
    } else {
        return a.X < b.X;
    }
}

int w[N], where[N], perm[N];
point p[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y >> w[i];
        p[i] = point(x, y);
    }

    iota(perm, perm + n, 0);
    sort(perm, perm + n, [&](int i, int j) {
        return comp(p[i], p[j]);
    });

    segtree *maxi = new segtree();
    for (int i = 0; i < n; ++i) {
        maxi->update(i, w[perm[i]], 0, n - 1);
        where[perm[i]] = i;
    }

    vector<tuple<point, int, int>> vec;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i != j && comp(p[i], p[j])) {
                vec.push_back({p[j] - p[i], i, j});
            }
        }
    }

    sort(vec.begin(), vec.end(), [&](auto i, auto j) {
        if (cross(get<0>(i), get<0>(j)) == 0) {
            if (get<1>(i) == get<1>(j)) {
                return comp(p[get<2>(i)], p[get<2>(j)]);
            }
            return comp(p[get<1>(i)], p[get<1>(j)]);
        }
        return cross(get<0>(i), get<0>(j)) < 0;
    });

    long long ans = maxi->maxi;
    for (int i = 0, j = 0; i < (int) vec.size(); i = j) {
        while (j < (int) vec.size() && cross(get<0>(vec[i]), get<0>(vec[j])) == 0) {
            auto [v, a, b] = vec[j++];
            maxi->update(where[a], w[b], 0, n - 1);
            maxi->update(where[b], w[a], 0, n - 1);
            swap(where[a], where[b]);
        }
        ans = max(ans, maxi->maxi);
    }

    cout << ans << "\n";
}

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