Cod sursa(job #1405014)

Utilizator zhm248Mustatea Radu zhm248 Data 28 martie 2015 19:19:57
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>
using namespace std;
long long v[400005];
struct Doica
{
    long long x;
    int y;
};
Doica v1[200005],v2[200005];
int main()
{
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    int n,i,x,y,poz=300000,lmin=300000;
    scanf("%d",&n);
    long long max;
    max=((-1)*10000)*200000;
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        if(y==0)
            x*=(-1);
        v[i]=v[i-1]+(1LL*x);
    }
    for(i=n+1;i<2*n;++i)
    {
        v[i]=v[n]+v[i-n];
    }
    for(i=2;i<=n;++i)
    {
        if(v1[i-1].x<v[i-1])
        {
            v1[i].x=v1[i-1].x;
            v1[i].y=v1[i-1].y;
        }
        else
        {
            v1[i].x=v[i-1];
            v1[i].y=i-1;
        }
    }
    v2[n-1].x=v[n-1];
    v2[n-1].y=n-1;
    for(i=n-2;i>=1;--i)
    {
        if(v[i]<v2[i+1].x)
        {
            v2[i].x=v[i];
            v2[i].y=i;
        }
        else
        {
            v2[i].x=v2[i+1].x;
            v2[i].y=v2[i+1].y;
        }
    }
    for(i=1;i<=n;++i)
    {
        if(max<v[i]-v1[i].x)
        {
            max=v[i]-v1[i].x;
            poz=v1[i].y+1;
            lmin=i-v1[i].y;
        }
    }
    for(i=1;i<=n;++i)
    {
        if(max<v[i+n]-v2[i].x)
        {
            max=v[i+n]-v2[i].x;
            poz=v2[i].y+1;
            lmin=i+n-v2[i].y;
        }
    }
    printf("%lld ",max);
    printf("%d %d\n",poz,lmin);
    return 0;
}