제출 #521405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
521405		tengiz05	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1034 ms	33496 KiB

bulldozer

#include <bits/stdc++.h>

using i64 = long long;

struct Info {
    i64 pr, sf;
    i64 sum;
    i64 ans;
    Info(i64 x = 0) : pr(std::max(0LL, x)), sf(std::max(0LL, x)), sum(x), ans(std::max(0LL, x)) {}
};
Info operator+(const Info &a, const Info &b) {
    Info res;
    res.pr = std::max(a.pr, a.sum + b.pr);
    res.sf = std::max(b.sf, a.sf + b.sum);
    res.sum = a.sum + b.sum;
    res.ans = std::max({a.ans, b.ans, a.sf + b.pr});
    return res;
}
template<class Info,
    class Merge = std::plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    std::vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
    SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = merge(info[2 * p], info[2 * p + 1]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};

struct Point {
    int x, y;
    int val;
    bool operator<(const Point &p) {
        return std::pair(x, y) < std::pair(p.x, p.y);
    }
};

struct Line {
    int a, b;
    int i, j;
    bool operator<(const Line &p) {
        i64 x = 1LL * a * p.b - 1LL * b * p.a;
        if (x == 0)
            return std::pair(i, j) < std::pair(p.i, p.j);
        return x > 0;
    }
};
bool same(const Line &a, const Line &b) {
    return 1LL * a.a * b.b == 1LL * a.b * b.a;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<Point> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i].x >> a[i].y >> a[i].val;
    }
    
    std::sort(a.begin(), a.end());
    
    if (n == 1) {
        std::cout << std::max(a[0].val, 0) << "\n";
        return 0;
    }
    
    std::vector<Line> v;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            v.push_back({a[j].x - a[i].x, a[j].y - a[i].y, i, j});
        }
    }
    
    std::sort(v.begin(), v.end());
    
    SegmentTree<Info> s(n);
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        s.modify(i, a[i].val);
        pos[i] = i;
    }
    
    i64 ans = s.info[1].ans;
    
    for (int i = 0; i < int(v.size()); i++) {
        int x = v[i].i, y = v[i].j;
        std::swap(pos[x], pos[y]);
        s.modify(pos[x], a[x].val);
        s.modify(pos[y], a[y].val);
        if (i + 1 < int(v.size()) && same(v[i], v[i + 1])) {
            continue;
        }
        ans = std::max(ans, s.info[1].ans);
    }
    
    std::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