Pagini recente » Atasamentele paginii Dictator | Cod sursa (job #75500) | Cod sursa (job #1065138)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <functional>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int n,v[400005],s[400005],sign,d[400005],st,k=1,smax,l,lmin,sact,lact,lenact;
int main()
{ int i;
f>>n;
for(i=1;i<=n;i++)
{f>>v[i]>>sign;
if (!sign) v[i]*=-1;
}
for(i=n+1;i<=2*n;i++)
v[i]=v[i-n];
n*=2;
k=1; d[1]=1; smax=v[1]; l=1; lmin=1;
st=1;
s[0]=0;
for(i=1;i<=n;i++)
s[i]=s[i-1]+v[i];
for(i=2;i<=n;i++)
{ while(st<k && i-d[st]>(n/2))
{st++; }
//if (s[i]<0) cout<<" ";
//cout<<s[i]-s[d[st]]<<" ";
sact=s[i]-s[d[st]];
lact=(d[st]+1)%(n/2); if (!lact) lact=(n/2);
lenact=i-d[st];
if (sact>smax || (sact==smax && lact<l) || (sact==smax && lact==l && lenact<lmin))
{ smax=sact;
l=lact; lmin=lenact;
}
while(k>=st && s[d[k]]>=s[i])
k--;
k++; d[k]=i;
}
g<<smax<<" "<<l<<" "<<lmin;
return 0;
}