Pagini recente » Cod sursa (job #1034629) | Rating Ionita Matei (Matei_Ionita) | Cod sursa (job #1831830) | Cod sursa (job #2953838) | Cod sursa (job #185726)
Cod sursa(job #185726)
#include <cstdio>
#define MAX_N 200000
int N,V[MAX_N],T[MAX_N],L[MAX_N];
long 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;
long maxl=0;
for(i = 1; i<=N; i++)
{
M[i] = max((S[i] = S[i-1] + V[i]), M[i-1]);
if(S[i] == S[i-1] + V[i])
T[i] = T[i-1] + 1;
else
T[i] = 1;
if(M[i] == S[i])
L[i] = T[i];
else
L[i] = L[i-1];
if(S[i] > maxl || !ps)
maxl = S[i],ps = i - T[i] + 1,lg = T[i];
}
for(i = 2; i<=N; i++)
{
if(S[N] - S[i-1] + M[i] < maxl) continue;
if((S[N] - S[i-1] + M[i] == maxl) && ((i > ps) || (L[i-1] + N - i + 1) > lg)) continue;
maxl = S[N] - S[i-1] + M[i];
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();
}