Pagini recente » Cod sursa (job #900716) | Cod sursa (job #2885839) | Cod sursa (job #718740) | Cod sursa (job #3196567) | Cod sursa (job #2069686)
#include <iostream>
#include <fstream>
#include <climits>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long int n, i, a, b, poz, P, P2, L, L2, j, v[400000], S[400000], Max[400000];
long long int mx=LONG_LONG_MIN, S_max, Suma;
int main()
{
f>>n;
for (i=0; i<n; i++) {
f>>a>>b;
if (b) v[i]=v[i+n]=a;
else v[i]=v[i+n]=-a;
}
S[0]=v[0];
for (S_max=Suma=v[0], P=poz=0, i=L=1; i<2*n; i++) {
if (Suma<0) { Suma=v[i]; poz=i; }
else { Suma+=v[i];
if (S_max<Suma) { S_max=Suma; P=poz; L=i-poz+1; }
}
S[i]=Suma;
}
j=P;
for (L=1, i=P+1; L<=n && i<n+P; i++)
if (S[i]>mx) { mx=S[i]; L+=i-j; j=i; }
S[0]=v[0];
for (i=1; i<n; i++) S[i]=S[i-1]+v[i];
Max[0]=S[0];
for (i=1; i<n; i++) {
if (S[i]>Max[i-1]) Max[i]=S[i];
else Max[i]=Max[i-1]; }
S_max=S[n-1]; P2=0;
for (i=1; i<n; i++) {
Suma=S[n-1]-S[i-1]+Max[i-1];
if (Suma>S_max) { S_max=Suma; P2=i; }
}
if (S_max<mx) g<<mx<<' '<<P+1<<' '<<L;
else g<<S_max<<' '<<P2+1<<' '<<n;
f.close();
g.close();
return 0;
}