Pagini recente » Cod sursa (job #520594) | Cod sursa (job #1261795) | Cod sursa (job #877627) | Cod sursa (job #1062428) | Cod sursa (job #53082)
Cod sursa(job #53082)
#include <cstdio>
void get_data();
void dynamics();
void print();
#define dim 200002
int A[dim];
int P[dim];
int N;
long S[dim];
long T[dim];
#define T (T+1)
#define A (A+1)
#define S (S+1)
#define P (P+1)
long Max, St, L;
int main()
{
get_data();
dynamics();
print();
return 0;
}
void get_data()
{
freopen("buline.in", "r", stdin);
long i;
int code;
for(scanf("%d", &N), i=1; i<=N; ++i)
{
scanf("%d %d", A+i, &code);
A[i] *= !code ? -1 : 1;
}
fclose(stdin);
}
void dynamics()
{
long i;
S[1] = A[1];
T[1] = S[1];
P[1] = 1;
for(i=2; i<=N; ++i)
{
S[i] = S[i-1] + A[i];
if(T[i-1] > S[i])
{
T[i] = T[i-1];
P[i] = P[i-1];
}
else if(S[i] > T[i-1])
{
T[i] = S[i];
P[i] = i;
}
}
Max = - 0x3f3f3f3f;
A[0] = Max;
for(i=0; i<=N; ++i)
{
if(T[i-1] + S[N] - S[i] > Max)
{
Max = T[i-1] + S[N] - S[i];
St = i + 1;
L = P[i-1] + N - i;
}
if(A[i] > Max)
{
Max = A[i];
St = i;
L = 1;
}
}
}
void print()
{
freopen("buline.out", "w", stdout);
if(St > N) St -= N;
printf("%ld %ld %ld", Max, St, L);
fclose(stdout);
}