Pagini recente » Cod sursa (job #516847) | Cod sursa (job #577703) | Cod sursa (job #2722952) | Cod sursa (job #768112) | Cod sursa (job #2548462)
#include <fstream>
#include <climits>
#define dim 200010
using namespace std;
int a[2*dim];
int s[2*dim];
int d[2*dim];
int i,n,p,u,x,Max,pr,l;
int main() {
ifstream fin("buline.in");
ofstream fout("buline.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>a[i]>>x;
if (x==0) a[i]=-a[i];
a[n+i]=a[i];
}
for (i=1;i<=2*n;i++) {
s[i]=a[i]+s[i-1];
}
Max=-INT_MIN;
p=1;
///fac un deque cu indicii la care incep sexventele de lungime maxima
///fiecare element poate ori sa fie adaugat la o secventa anterioara oria
for (i=1;i<=2*n;i++) {
while (p<=u&&s[i]<s[d[u]]) u--;
d[++u]=i;
if (i-d[p]+1==n+1) p++;
if (s[i]-s[d[p]]>Max) {
Max=s[i]-s[d[p]];
pr=d[p]+1;
l=i-d[p];
}
}
fout<<Max<<" "<<pr<<" "<<l;
return 0;
}