제출 #224570

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224570		dolphingarlic	Bulldozer (JOI17_bulldozer)	C++14	5 / 100	5 ms	384 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 Obstacle {
    ll x, y, v;

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

int n;

void build(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        ll v = max(obstacles[l].v, 0ll);
        segtree[node] = {v, v, obstacles[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 >> obstacles[i].x >> obstacles[i].y >> obstacles[i].v;
    sort(obstacles + 1, obstacles + n + 1);
    build();

    cout << segtree[1].best;
    return 0;
}

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