oj.uz

Submission #590532

# Submission time Handle Problem Language Result Execution time Memory
590532 2022-07-06T05:32:49 Z 이동현(#8415) Bulldozer (JOI17_bulldozer) C++17
25 / 100
 2000 ms 62960 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;
        }
        ans = max(ans, tr[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]);
        }
        ans = max(ans, tr[1]);
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 5 ms 484 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 524 KB Output is correct
6 Correct 5 ms 484 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 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 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 520 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 5 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 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 4 ms 488 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 4 ms 572 KB Output is correct
26 Correct 6 ms 468 KB Output is correct
27 Correct 7 ms 536 KB Output is correct
28 Correct 6 ms 468 KB Output is correct
29 Correct 5 ms 612 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 4 ms 468 KB Output is correct
32 Correct 5 ms 468 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 520 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 5 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 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 4 ms 488 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 4 ms 572 KB Output is correct
26 Correct 6 ms 468 KB Output is correct
27 Correct 7 ms 536 KB Output is correct
28 Correct 6 ms 468 KB Output is correct
29 Correct 5 ms 612 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 4 ms 468 KB Output is correct
32 Correct 5 ms 468 KB Output is correct
33 Execution timed out 2064 ms 62960 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 5 ms 520 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 5 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 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 4 ms 488 KB Output is correct
23 Correct 4 ms 468 KB Output is correct
24 Correct 5 ms 468 KB Output is correct
25 Correct 4 ms 572 KB Output is correct
26 Correct 6 ms 468 KB Output is correct
27 Correct 7 ms 536 KB Output is correct
28 Correct 6 ms 468 KB Output is correct
29 Correct 5 ms 612 KB Output is correct
30 Correct 5 ms 468 KB Output is correct
31 Correct 4 ms 468 KB Output is correct
32 Correct 5 ms 468 KB Output is correct
33 Execution timed out 2064 ms 62960 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 5 ms 484 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 524 KB Output is correct
6 Correct 5 ms 484 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 4 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 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 4 ms 468 KB Output is correct
17 Correct 4 ms 468 KB Output is correct
18 Correct 5 ms 520 KB Output is correct
19 Correct 6 ms 468 KB Output is correct
20 Correct 5 ms 468 KB Output is correct
21 Correct 5 ms 468 KB Output is correct
22 Correct 5 ms 468 KB Output is correct
23 Correct 5 ms 468 KB Output is correct
24 Correct 4 ms 596 KB Output is correct
25 Correct 5 ms 468 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 0 ms 340 KB Output is correct
36 Correct 5 ms 468 KB Output is correct
37 Correct 4 ms 488 KB Output is correct
38 Correct 4 ms 468 KB Output is correct
39 Correct 5 ms 468 KB Output is correct
40 Correct 4 ms 572 KB Output is correct
41 Correct 6 ms 468 KB Output is correct
42 Correct 7 ms 536 KB Output is correct
43 Correct 6 ms 468 KB Output is correct
44 Correct 5 ms 612 KB Output is correct
45 Correct 5 ms 468 KB Output is correct
46 Correct 4 ms 468 KB Output is correct
47 Correct 5 ms 468 KB Output is correct
48 Execution timed out 2064 ms 62960 KB Time limit exceeded
49 Halted 0 ms 0 KB -