Pagini recente » Cod sursa (job #1708706) | Cod sursa (job #2847637) | Cod sursa (job #2918176) | Cod sursa (job #2570374) | Cod sursa (job #53350)
Cod sursa(job #53350)
#include <cstdio>
long N;
long Smax = -0x3f3f3f3f;
long Poz;
long L;
#define dim 200001
int A[dim];
long S1[dim], S2[dim], T1[dim], T2[dim], P1[dim], P2[dim];
void get_data();
void dynamics();
void print();
int main()
{
get_data();
dynamics();
print();
return 0;
}
#define input "buline.in"
void get_data()
{
freopen(input, "rt", stdin);
long i;
int code;
for(scanf("%ld", &N), i=1; i<=N; ++i)
{
scanf("%ld %d", A+i, &code);
A[i] *= !code ? -1 : 1;
}
fclose(stdin);
}
void dynamics()
{
long i;
long S;
long P;
long len;
int c;
S1[1] = A[1];
T1[1] = A[1];
P1[1] = 1;
for(i=2; i<=N; ++i)
{
S1[i] = S1[i-1] + A[i];
if(T1[i-1] > S1[i])
{
T1[i] = T1[i-1];
P1[i] = P1[i-1];
}
else
{
T1[i] = S1[i];
P1[i] = i;
}
}
S2[N] = A[N];
T2[N] = A[N];
P2[N] = N;
for(i=N-1; i; --i)
{
S2[i] = S2[i+1] + A[i];
if(T2[i+1] > S2[i])
{
T2[i] = T2[i+1];
P2[i] = P2[i+1];
}
else
{
T2[i] = S2[i];
P2[i] = i;
}
}
for(i=1; i<=N; ++i)
{
S = T1[i] + T2[i];
if(P1[i] == P2[i])
{
S -= A[i];
c = 0;
}
else c = 1;
if(S > Smax)
{
Smax = S;
Poz = P2[i];
L = P1[i] + N - P2[i] + c;
}
S = T1[i];
if(S > Smax)
{
Smax = S;
Poz = 1;
L = P1[i];
}
S = T2[i];
if(S > Smax)
{
Smax = S;
Poz = P2[i];
L = N - P2[i] + 1;
}
}
S = 0;
P = 1;
len = 0;
for(i=1; i<=N; ++i)
{
S += A[i];
++ len;
if(S > Smax)
{
Smax = S;
Poz = P;
L = len;
}
if(S < 0)
{
S = 0;
len = 0;
P = i + 1;
}
}
}
#define output "buline.out"
void print()
{
freopen(output, "wt", stdout);
printf("%ld %ld %ld", Smax, Poz, L);
fclose(stdout);
}