oj.uz

Submission #103919

# Submission time Handle Problem Language Result Execution time Memory
103919 2019-04-03T09:17:26 Z Bodo171 Bulldozer (JOI17_bulldozer) C++14
0 / 100
 4 ms 512 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
struct point
{
    long long x,y,val;
}v[nmax];
struct line
{
    long long nr,nm;
    int i1,i2;
}pp[nmax*nmax/2];
struct node
{
    long long mxsuf,mxpref,sum;
}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 update(int nod,int l,int r,int poz,long long val)
{
    A[poz]=val;
}
void query(int nod,int l,int r,int st,int dr)
{
    long long sum=0;
    for(int i=st;i<=dr;i++)
    {
        sum+=A[i];
        if(sum>ans.mxpref)
            ans.mxpref=1LL*sum;
    }
    sum=0;
    for(int i=dr;i>=st;i--)
    {
        sum+=A[i];
        if(sum>ans.mxsuf)
            ans.mxsuf=1LL*sum;
    }
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].val;
    }
    sort(v+1,v+n+1,compP);
    for(i=1;i<=n;i++)
    {
        ord[i]=i;
        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=v[i].val+v[j].val;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(i>=1)query(1,1,n,1,i-1);
        act+=ans.mxsuf;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(i<n) query(1,1,n,i+1,n);
        act+=ans.mxpref;
        if(act>mx)
            mx=1LL*act;
    }
    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;
    }
    sort(pp+1,pp+nr+1,compL);
    for(i=1;i<=nr;i++)
    {
        I=pp[i].i1;J=pp[i].i2;
        swap(ord[I],ord[J]);
      //  if(abss(ord[I]-ord[J])!=1)
     //       cout<<"assert\n";
        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=v[I].val+v[J].val;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(poz>=1)query(1,1,n,1,poz-1);
        act+=ans.mxsuf;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(poz<n)query(1,1,n,poz+2,n);
        act+=ans.mxpref;
        if(act>mx)
        mx=1LL*act;
    }
    cout<<mx;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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