oj.uz

Submission #103951

# Submission time Handle Problem Language Result Execution time Memory
103951 2019-04-03T12:54:30 Z Bodo171 Bulldozer (JOI17_bulldozer) C++14
25 / 100
 2000 ms 31736 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
struct point
{
    int x,y,val;
}v[nmax];
struct line
{
    int nr,nm;
    int i1,i2;
}pp[nmax*nmax/2];
struct node
{
    long long mxsuf,mxpref,sum;
}arb[4*nmax],ans;
pair<long long,long long> lin=make_pair(-2*1000*1000*1000-1,1);
bool compP(point unu,point doi)
{
    return (1LL*unu.x*lin.first+1LL*unu.y*lin.second<1LL*doi.x*lin.first+1LL*doi.y*lin.second);
}
bool compL(line unu,line doi)
{
    return (1LL*unu.nr*doi.nm<1LL*unu.nm*doi.nr);
}
int ord[nmax];
long long A[nmax];
int n,i,j,nr,I,J,poz;
long long act,mx;
void mrg(node &A,node B,node C)
{
    A.sum=1LL*B.sum+C.sum;
    A.mxpref=max(B.mxpref,B.sum+C.mxpref);
    A.mxsuf=max(C.mxsuf,C.sum+B.mxsuf);
}
void update(int nod,int l,int r,int poz,long long val)
{
    if(l==r)
    {
        arb[nod].mxpref=arb[nod].mxsuf=max(val,0LL);
        arb[nod].sum=val;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m,poz,val);
    else update(2*nod+1,m+1,r,poz,val);
    mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        mrg(ans,ans,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m,st,dr);
    if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
void slv()
{
    for(int i=1;i<=n;i++)
    {
        act=0;
        for(int j=i;j<=n;j++)
        {
            act+=v[j].val;
            if(act>mx)
                mx=act;
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n;
    bool solve0=1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].val;
        mx=max(mx,1LL*v[i].val);
        if(v[i].y!=0)
            solve0=0;
    }
    sort(v+1,v+n+1,compP);
    if(solve0)
    {
        slv();
        cout<<mx;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        ord[i]=i;
        if(v[i-1].x==v[i].x&&i>1)update(1,1,n,i-1,v[i].val+v[i-1].val);
        else update(1,1,n,i,v[i].val);
    }
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(v[i].x==v[j].x)
    {
        act=0;
        update(1,1,n,i,v[i].val);
        update(1,1,n,j,v[j].val);
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(i>=1)query(1,1,n,1,i);
        act+=ans.mxsuf;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(j<=n) query(1,1,n,j,n);
        act+=ans.mxpref;
        if(act>mx)
            mx=1LL*act;
        update(1,1,n,i,v[i].val+v[j].val);
        update(1,1,n,j,0);
    }
    else
    {
        pp[++nr]={v[j].y-v[i].y,v[j].x-v[i].x,i,j};
        if(pp[nr].nm<0)
            pp[nr].nr*=-1,pp[nr].nm*=-1;
    }
    for(i=1;i<=n;i++)
        update(1,1,n,i,v[i].val);
    sort(pp+1,pp+nr+1,compL);
    int lim;
    for(i=1;i<=nr;i++)
    {
        for(j=i;j<=nr&&1LL*pp[i].nm*pp[j].nr==1LL*pp[i].nr*pp[j].nm;j++);
        j--;
        lim=j;
        for(j=i;j<=lim;j++)
        {
           I=pp[j].i1;
           J=pp[j].i2;
           update(1,1,n,ord[I],v[I].val+v[J].val);
           update(1,1,n,ord[J],0);
        }
        for(j=i;j<=lim;j++)
        {
            I=pp[j].i1;
            J=pp[j].i2;
            swap(ord[I],ord[J]);
            poz=min(ord[I],ord[J]);
            update(1,1,n,ord[I],v[I].val);
            update(1,1,n,ord[J],v[J].val);
            act=0;
            ans.mxpref=ans.sum=ans.mxsuf=0;
            if(poz>=1)query(1,1,n,1,poz);
            act+=ans.mxsuf;
            ans.mxpref=ans.sum=ans.mxsuf=0;
            if(poz+1<=n)query(1,1,n,poz+1,n);
            act+=ans.mxpref;
            if(act>mx)
                mx=1LL*act;
           update(1,1,n,ord[I],v[I].val+v[J].val);
           update(1,1,n,ord[J],0);
        }
        for(j=i;j<=lim;j++)
        {
           I=pp[j].i1;
           J=pp[j].i2;
           update(1,1,n,ord[I],v[I].val);
           update(1,1,n,ord[J],v[J].val);
        }
        i=lim;
    }
    cout<<mx;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

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