Mai intai trebuie sa te autentifici.
Cod sursa(job #185708)
Utilizator | Data | 25 aprilie 2008 22:03:28 | |
---|---|---|---|
Problema | Buline | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.2 kb |
#include <cstdio>
#define MAX_N 200000
int N,V[MAX_N],T[MAX_N],L[MAX_N];
long long S[MAX_N],M[MAX_N];
inline long long max(long long a,long 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 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-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("%lld %d %d",maxl,ps,lg);
}
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
read();
solve();
}