제출 #642531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642531		elkernos	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	774 ms	66596 KiB

bulldozer

#include <bits/stdc++.h>

using namespace std;

#define int long long
struct T {
    int l, r, sum, ans;
    T operator+(T he) { return {max(l, sum + he.l), max(r + he.sum, he.r), sum + he.sum, max({ans, he.ans, r + he.l})}; }
    void ini(int v)
    {
        sum = v;
        l = r = ans = max(0LL, v);
    }
};
struct P {
    int x, y, add;
    bool operator<(P he) { return tie(x, y) < tie(he.x, he.y); }
    void read() { cin >> x >> y >> add; }
};
struct V {
    int dx, dy, a, b;
    bool operator<(V he) { return make_tuple(dy * he.dx, a, b) < make_tuple(he.dy * dx, he.a, he.b); }
};

int n;
vector<T> tree;
vector<P> points;

#define m (l + r) / 2
#define lc 2 * v
#define rc 2 * v + 1
void build(int v = 1, int l = 0, int r = n - 1)
{
    if(l == r) {
        tree[v].ini(points[l].add);
    }
    else {
        build(lc, l, m), build(rc, m + 1, r);
        tree[v] = tree[lc] + tree[rc];
    }
}
void update(int where, int to, int v = 1, int l = 0, int r = n - 1)
{
    if(l == r) {
        tree[v].ini(to);
    }
    else {
        if(where <= m) {
            update(where, to, lc, l, m);
        }
        else {
            update(where, to, rc, m + 1, r);
        }
        tree[v] = tree[lc] + tree[rc];
    }
}
#undef m
#undef lc
#undef rc

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    points.resize(n);
    tree.resize(4 * n);
    vector<int> gdz(n);
    for(int i = 0; i < n; i++) {
        points[i].read();
        gdz[i] = i;
    }
    sort(points.begin(), points.end());
    vector<V> wek;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            wek.push_back({points[j].x - points[i].x, points[j].y - points[i].y, i, j});
        }
    }
    sort(wek.begin(), wek.end());
    build();
    int ans = tree[1].ans;
    int m = (int)wek.size();
    for(int i = 0; i < m; i++) {
        auto [a, b] = tie(wek[i].a, wek[i].b);
        update(gdz[a], points[b].add);
        update(gdz[b], points[a].add);
        swap(gdz[a], gdz[b]);
        if(i == m - 1 || wek[i].dy * wek[i + 1].dx != wek[i + 1].dy * wek[i].dx) {
            ans = max(ans, tree[1].ans);
        }
    }
    cout << ans << '\n';
}

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