oj.uz

Submission #122697

# Submission time Handle Problem Language Result Execution time Memory
122697 2019-06-29T06:55:31 Z 송준혁(#3002) Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 66300 KB 
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

int N;
int cnt[2020], t;
LL ans;

struct Point{
    LL x, y, w;
    int p, q;
} P[2020];
vector<Point> E;

struct Node{
    LL Lmax, Rmax, Sum, Max;
    Node operator+(const Node &r)const{
        Node ret;
        ret.Lmax = max(Lmax, Sum+r.Lmax);
        ret.Rmax = max(r.Rmax, Rmax+r.Sum);
        ret.Sum = Sum + r.Sum;
        ret.Max = max(Max, r.Max);
        ret.Max = max(ret.Max, Rmax+r.Lmax);
        return ret;
    }
} T[10101];

void update(int id, int s, int e, int t, LL v){
    if (t < s || e < t) return;
    if (s == e){
        T[id].Sum += v;
        T[id].Lmax = max(0ll, T[id].Sum);
        T[id].Rmax = max(0ll, T[id].Sum);
        T[id].Max = max(0ll, T[id].Sum);
        return;
    }
    int mid = (s+e)/2;
    update(id*2, s, mid, t, v);
    update(id*2+1, mid+1, e, t, v);
    T[id] = T[id*2] + T[id*2+1];
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &P[i].x, &P[i].y, &P[i].w);
    sort(P+1, P+N+1, [&](Point a, Point b){
        if (a.x == b.x) return a.y > b.y;
        return a.x < b.x;
    });
    for (int i=1; i<N; i++) for (int j=i+1; j<=N; j++){
        E.push_back((Point){P[j].x-P[i].x, P[j].y-P[i].y, 0, i, j});
        cnt[j]++;
    }
    sort(E.begin(), E.end(), [&](Point a, Point b){
         if (a.x == 0 && b.x == 0) return a.y < b.y;
         if (a.x == 0) return true;
         if (b.x == 0) return false;
         return a.y*b.x < b.y*a.x;
    });
    for (int i=1; i<=N; i++) update(1, 0, N, cnt[i], P[i].w);
    ans = max(ans, T[1].Max);
    while (t < (int)E.size()){
        LL dx=E[t].x, dy=E[t].y;
        for (int i=t; i<(int)E.size() && (E[i].y*dx == dy*E[i].x || (dx == 0 && E[i].x == 0)); i++){
            update(1, 0, N, cnt[E[i].q], -P[E[i].q].w);
            cnt[E[i].q]--;
            update(1, 0, N, cnt[E[i].q], P[E[i].q].w);
        }
        ans = max(ans, T[1].Max);
        for (; t<(int)E.size() && (E[t].y*dx == dy*E[t].x || (dx == 0 && E[t].x == 0)); t++){
            update(1, 0, N, cnt[E[t].p], -P[E[t].p].w);
            cnt[E[t].p]++;
            update(1, 0, N, cnt[E[t].p], P[E[t].p].w);
        }
        ans = max(ans, T[1].Max);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:45:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%lld %lld %lld", &P[i].x, &P[i].y, &P[i].w);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 760 KB Output is correct
11 Correct 2 ms 316 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 252 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 10 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 764 KB Output is correct
30 Correct 7 ms 760 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 252 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 10 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 764 KB Output is correct
30 Correct 7 ms 760 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Execution timed out 2045 ms 66300 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 760 KB Output is correct
2 Correct 6 ms 760 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 6 ms 760 KB Output is correct
5 Correct 6 ms 760 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 6 ms 760 KB Output is correct
9 Correct 6 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 252 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 10 ms 760 KB Output is correct
27 Correct 6 ms 760 KB Output is correct
28 Correct 6 ms 760 KB Output is correct
29 Correct 6 ms 764 KB Output is correct
30 Correct 7 ms 760 KB Output is correct
31 Correct 6 ms 760 KB Output is correct
32 Correct 6 ms 760 KB Output is correct
33 Execution timed out 2045 ms 66300 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 5 ms 760 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 5 ms 760 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 5 ms 760 KB Output is correct
11 Correct 2 ms 316 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 6 ms 760 KB Output is correct
17 Correct 6 ms 760 KB Output is correct
18 Correct 6 ms 760 KB Output is correct
19 Correct 6 ms 760 KB Output is correct
20 Correct 6 ms 760 KB Output is correct
21 Correct 6 ms 760 KB Output is correct
22 Correct 6 ms 760 KB Output is correct
23 Correct 6 ms 760 KB Output is correct
24 Correct 6 ms 760 KB Output is correct
25 Correct 6 ms 760 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 252 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 376 KB Output is correct
34 Correct 2 ms 376 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 6 ms 760 KB Output is correct
37 Correct 6 ms 760 KB Output is correct
38 Correct 6 ms 760 KB Output is correct
39 Correct 6 ms 760 KB Output is correct
40 Correct 6 ms 760 KB Output is correct
41 Correct 10 ms 760 KB Output is correct
42 Correct 6 ms 760 KB Output is correct
43 Correct 6 ms 760 KB Output is correct
44 Correct 6 ms 764 KB Output is correct
45 Correct 7 ms 760 KB Output is correct
46 Correct 6 ms 760 KB Output is correct
47 Correct 6 ms 760 KB Output is correct
48 Execution timed out 2045 ms 66300 KB Time limit exceeded
49 Halted 0 ms 0 KB -