oj.uz

Submission #156375

# Submission time Handle Problem Language Result Execution time Memory
156375 2019-10-05T11:43:21 Z georgerapeanu Bulldozer (JOI17_bulldozer) C++11
0 / 100
 4 ms 636 KB 
#include <cstdio>
#include <algorithm>

using namespace std;

struct point_t{
    int x,y,c;

    bool operator < (const point_t &other)const{
        if(x != other.x){
            return x < other.x;
        }
        return y < other.y;
    }
};

struct line_t{
    int a,b;
    int i,j;
};

struct node_t{
    long long pref_sum;
    long long suff_sum;
    long long best_sum;
    long long total_sum;

    node_t(long long a = 0LL){
        pref_sum = max(a,0LL);
        suff_sum = max(a,0LL);
        total_sum = a;
        best_sum = max(a,0LL);
    }

    node_t operator + (const node_t &other)const{
        node_t ans;
        ans.pref_sum = max(this->pref_sum,this->total_sum + other.pref_sum);
        ans.suff_sum = max(other.suff_sum,other.total_sum + this->suff_sum);
        ans.total_sum = this->total_sum + other.total_sum;
        ans.best_sum = max(max(this->best_sum,other.best_sum),this->suff_sum + other.pref_sum);
        return ans;
    }
};

int n;
int ord[2005];
point_t v[2005];
line_t lines[2000 * 2000 + 5];
node_t aint[8005];

void build(int nod,int st,int dr){

    if(st == dr){
        aint[nod] = node_t(v[st].c);
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update(int nod,int st,int dr,int pos,int val){
    if(dr < pos || st > pos){
        return ;
    }

    if(st == dr){
        aint[nod] = node_t(val);
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,pos,val);
    update(nod * 2 + 1,mid + 1,dr,pos,val);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

int main(){

    scanf("%d",&n);

    for(int i = 1;i <= n;i++){
        scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].c);
    }

    sort(v + 1,v + 1 + n);

    int len = 0;

    for(int i = 1;i <= n;i++){
        for(int j = i + 1;j <= n;j++){
            lines[++len] = {v[j].x - v[i].x,v[j].y - v[i].y,i,j};
        }
    }

    sort(lines + 1,lines + 1 + len,[&](line_t &a,line_t & b){return 1LL * a.b * b.a < 1LL * b.b * a.a;});

    for(int i = 1;i <= n;i++){
        ord[i] = i;
    }

    build(1,1,n);

    long long ans = 0;

    for(int i = 1;i <= len;i++){
        swap(ord[lines[i].i],ord[lines[i].j]);
        update(1,1,n,ord[lines[i].i],v[lines[i].i].c);
        update(1,1,n,ord[lines[i].j],v[lines[i].j].c);
        if(i == n || (1LL * lines[i].b * lines[i + 1].a < 1LL * lines[i + 1].b * lines[i].a)){
            ans = max(ans,aint[1].best_sum);
        }
    }

    printf("%lld\n",ans);

    return 0;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
bulldozer.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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