Cod sursa(job #2183194)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 22 martie 2018 21:47:36
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#define val first
#define pos second

/// TONI BO$$ was here
/// #MLC

using namespace std;

int v[200001];
pair<int,int> smin[200001],smax[200001];

int main()
{
    int n,s,i,c,rez,p,l;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    s=0;
    for(i=1; i<=n; i++)
    {
        scanf("%d%d",&v[i],&c);
        if(c==0)
            v[i]=-v[i];
        s+=v[i];
    }
    smin[1]=smax[1]={v[1],1};
    for(i=2; i<=n; i++)
    {
        if(smin[i-1].val>0)
            smin[i]={v[i],i};
        else
            smin[i]={smin[i-1].val+v[i],smin[i-1].pos};
        if(smax[i-1].val<0)
            smax[i]={v[i],i};
        else
            smax[i]={smax[i-1].val+v[i],smax[i-1].pos};
    }
    rez=v[1];
    p=1;
    l=1;
    for(i=1; i<=n; i++)
    {
        if(s-smin[i].val>rez)
        {
            rez=s-smin[i].val;
            p=i+1;
            l=n-(i-smin[i].pos+1);
        }
        else
            if(s-smin[i].val==rez && p>i+1)
            {
                p=i+1;
                l=n-(i-smin[i].pos+1);
            }
            else
                if(s-smin[i].val==rez && p==smin[i].pos && l>n-(i-smin[i].pos+1))
                    l=n-(i-smin[i].pos+1);
        if(smax[i].val>rez)
        {
            rez=smax[i].val;
            p=smax[i].pos;
            l=i-p+1;
        }
        else
            if(smax[i].val==rez && p>smax[i].pos)
            {
                p=smax[i].pos;
                l=i-p+1;
            }
            else
                if(smax[i].val==rez && p==smax[i].pos && l>i-p+1)
                    l=i-p+1;
    }
    printf("%d %d %d",rez,p,l);

    return 0;
}