Pagini recente » Cod sursa (job #1494543) | Cod sursa (job #185737)
Cod sursa(job #185737)
#include <cstdio>
#define MAX_N 200000
int N,V[MAX_N],L[MAX_N];
int S[MAX_N],M[MAX_N];
inline long max(long a, long b)
{
return (a > b)? a : b;
}
void read()
{
scanf("%d",&N);
for(int i=1,x,y; i<=N; i++)
{
scanf("%d %d",&x,&y);
V[i] = (y)? x : -x;
}
}
void solve()
{
int i,ps=0,lg;
int maxl=0,min = 0;
for(i = 1; i<=N; i++)
{
M[i] = max((S[i] = S[i-1] + V[i]), M[i-1]);
if(M[i] == S[i])
L[i] = i;
else
L[i] = L[i-1];
if(S[i-1] < S[min])
min = i-1;
if(S[i] - S[min] > maxl || !ps)
maxl = S[i] - S[min],ps = i - i + min + 1,lg = i - min;
}
for(i = 2; i<=N; i++)
{
if(S[N] - S[i-1] + M[i-1] < maxl) continue;
if((S[N] - S[i-1] + M[i-1] == maxl) && ((i > ps) || (L[i-1] + N - i + 1) > lg)) continue;
maxl = S[N] - S[i-1] + M[i-1];
ps = i;
lg = L[i-1] + N - i + 1;
}
printf("%ld %d %d",maxl,ps,lg);
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
read();
solve();
}