oj.uz

Submission #590530

# Submission time Handle Problem Language Result Execution time Memory
590530 2022-07-06T05:28:36 Z 이동현(#8415) Bulldozer (JOI17_bulldozer) C++17
0 / 100
 7 ms 524 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int NS = 2004;
int n;
vector<int> a[2004];
struct Line{
    int id1, id2, dx, dy;
    Line(){}
    Line(int id1, int id2, int dx, int dy):id1(id1), id2(id2), dx(dx), dy(dy){}
    bool operator<(const Line&r)const{
        return vector<int>{dx * r.dy, id1, id2} < vector<int>{r.dx * dy, r.id1, r.id2};
    }
};
Line srt[2004 * 2004];
int num[2004], pos[2004], chk[2004];
int srtN;

int tr[NS * 4], lmax[NS * 4], rmax[NS * 4], sum[NS * 4];

void push(int x, int s, int e, int p, int val){
    if(p < s || p > e) return;
    if(s == e){
        tr[x] += val; sum[x] += val;
        lmax[x] = rmax[x] = max(0ll, tr[x]);
        return;
    }
    int m = s + e >> 1;
    push(x * 2, s, m, p, val), push(x * 2 + 1, m + 1, e, p, val);
    tr[x] = max({tr[x * 2], tr[x * 2 + 1], rmax[x * 2] + lmax[x * 2 + 1]});
    rmax[x] = max({rmax[x * 2 + 1], sum[x * 2 + 1] + rmax[x * 2]});
    lmax[x] = max({lmax[x * 2], sum[x * 2] + lmax[x * 2 + 1]});
    sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

signed main(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        a[i].resize(3);
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    if(n == 1){
        cout << max(0ll, a[0][2]) << '\n';
        return 0;
    }
    sort(a, a + n);
    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            srt[srtN++] = Line(i, j, a[j][0] - a[i][0], a[j][1] - a[i][1]);
        }
    }
    sort(srt, srt + srtN);
    memset(num, -1, sizeof(num));
    for(int i = 0; i < n; ++i){
        pos[i] = i;
        push(1, 0, n - 1, i, a[i][2]);
    }
    int ans = 0;
    for(int i = 0; i < srtN;){
        int j = i;
        while(j < srtN && srt[i].dx * srt[j].dy == srt[i].dy * srt[j].dx){
            ++j;
        }
        for(int k = i; k < j; ++k){
            if(num[srt[k].id1] == -1) num[srt[k].id1] = srt[k].id1;
            if(num[srt[k].id2] == -1) num[srt[k].id2] = srt[k].id2;
            num[srt[k].id2] = min(num[srt[k].id2], srt[k].id1);
        }
        for(int k = i; k < j; ++k){
            if(!chk[srt[k].id2]){
                chk[srt[k].id2] = 1;
                push(1, 0, n - 1, pos[srt[k].id2], -a[srt[k].id2][2]);
                push(1, 0, n - 1, pos[num[srt[k].id2]], a[srt[k].id2][2]);
            }
        }
        if(tr[1] == 19){
            cout << srt[i].dx << ' ' << srt[i].dy << endl;
        }
        ans = max(ans, tr[1]);
        for(int k = i; k < j; ++k){
            if(chk[srt[k].id2]){
                chk[srt[k].id2] = 0;
                push(1, 0, n - 1, pos[srt[k].id2], a[srt[k].id2][2]);
                push(1, 0, n - 1, pos[num[srt[k].id2]], -a[srt[k].id2][2]);
            }
        }
        for(int k = i; k < j; ++k){
            num[srt[k].id1] = num[srt[k].id2] = -1;
        }

        for(int k = i; k < j; ++k){
            swap(pos[srt[k].id1], pos[srt[k].id2]);
            push(1, 0, n - 1, pos[srt[k].id1], a[srt[k].id1][2] - a[srt[k].id2][2]);
            push(1, 0, n - 1, pos[srt[k].id2], a[srt[k].id2][2] - a[srt[k].id1][2]);
        }
        i = j;
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

bulldozer.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int)':
bulldozer.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     int m = s + e >> 1;
      |             ~~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 520 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 5 ms 524 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 520 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 520 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 5 ms 524 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 520 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 520 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 5 ms 524 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 6 ms 520 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Incorrect 0 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -