Cod sursa(job #1525189)

Utilizator SoniaFlorinaHorchidan Sonia-Florina SoniaFlorina Data 14 noiembrie 2015 20:16:04
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <climits>
#include <iostream>
using namespace std;
ifstream in ("buline.in");
ofstream out("buline.out");
int n,suma[400000],dek[400000],v[400000];

int main()
{ in>>n;
int a,b,i;
int maxim=-INT_MAX,minim=0,prim,ultim,p=0,s=-INT_MAX,l=0;
for(i=1;i<=n;i++)
    {in>>a>>b;
    if(b==1)
        {v[i]=a;
        v[n+i]=a;}
    else
        {v[i]=(-1)*a;
        v[n+i]=(-1)*a;}
    suma[i]=suma[i-1]+v[i];}
for(i=n;i<=2*n;i++)
    suma[i]=suma[i-1]+v[i];
  prim=1;
  ultim=0;
  for(i=1; i<=2*n; i++)
    {while(suma[i]<=suma[dek[ultim]] && prim<=ultim)
            ultim--;
    ultim++;
    dek[ultim]=i;
    if(dek[prim]<=i-n)
        prim++;
    if(s<suma[i]-suma[dek[prim]])
        {s=suma[i]-suma[dek[prim]];
        p=prim+1;
        l=i-prim;}

    }
 cout<<s<<' '<<p<<' '<<l;



    return 0;
}