제출 #224598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224598		dolphingarlic	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1127 ms	50108 KiB

bulldozer

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    ll l, r, tot, best;

    Node operator+(Node B) {
        return {max(l, tot + B.l), max(B.r, r + B.tot), tot + B.tot, max(max(best, B.best), r + B.l)};
    }
} segtree[8001];

struct Point {
    ll x, y, v;

    bool operator<(Point B) {
        if (x == B.x) return y < B.y;
        return x < B.x;
    }
} points[2001];

struct Line {
    ll dx, dy;
    int u, v;

    bool operator<(Line B) {
        if (dy * B.dx == B.dy * dx) return tie(u, v) < tie(B.u, B.v);
        return dy * B.dx < B.dy * dx;
    }
};
vector<Line> swaps;

int n, curr[2001];

void build(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        ll v = max(points[l].v, 0ll);
        segtree[node] = {v, v, points[l].v, v};
    } else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

void update(int pos, ll val, int node = 1, int l = 1, int r = n) {
    if (l == r) segtree[node] = {max(val, 0ll), max(val, 0ll), val, max(val, 0ll)};
    else {
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, val, node * 2 + 1, mid + 1, r);
        else update(pos, val, node * 2, l, mid);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> points[i].x >> points[i].y >> points[i].v;
        curr[i] = i;
    }
    sort(points + 1, points + n + 1);
    FOR(i, 1, n + 1) FOR(j, i + 1, n + 1) if (points[i].x != points[j].x)
        swaps.push_back({points[j].x - points[i].x, points[j].y - points[i].y, i, j});
    sort(swaps.begin(), swaps.end());

    build();
    ll ans = segtree[1].best;
    FOR(i, 0, swaps.size()) {
        update(curr[swaps[i].u], points[swaps[i].v].v);
        update(curr[swaps[i].v], points[swaps[i].u].v);
        swap(curr[swaps[i].u], curr[swaps[i].v]);

        if (i == swaps.size() - 1) ans = max(ans, segtree[1].best);
        else if (swaps[i].dy * swaps[i + 1].dx != swaps[i + 1].dy * swaps[i].dx) ans = max(ans, segtree[1].best);
    }
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:2:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
bulldozer.cpp:73:9:
     FOR(i, 0, swaps.size()) {
         ~~~~~~~~~~~~~~~~~~              
bulldozer.cpp:73:5: note: in expansion of macro 'FOR'
     FOR(i, 0, swaps.size()) {
     ^~~
bulldozer.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i == swaps.size() - 1) ans = max(ans, segtree[1].best);
             ~~^~~~~~~~~~~~~~~~~~~

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