oj.uz

Submission #122707

# Submission time Handle Problem Language Result Execution time Memory
122707 2019-06-29T07:02:19 Z 송준혁(#3002) Bulldozer (JOI17_bulldozer) C++14
5 / 100
 5 ms 504 KB 
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

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

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

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++){
        num++, cnt[j]++;
        E[num] = (Point){P[j].x-P[i].x, P[j].y-P[i].y, 0, i, j};
    }
    sort(E+1, E+num+1, [&](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 <= num){
        LL dx=E[t].x, dy=E[t].y;
        for (int i=t; i<=num && (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<=num && (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:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
bulldozer.cpp:44: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 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 480 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 2 ms 376 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 376 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 504 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 4 ms 480 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 2 ms 376 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 376 KB Output is correct
16 Incorrect 5 ms 504 KB Output isn't correct
17 Halted 0 ms 0 KB -