Pagini recente » Cod sursa (job #334033) | Cod sursa (job #2560329) | Cod sursa (job #1927543) | Cod sursa (job #2053577) | Cod sursa (job #2111775)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("buline.in");
ofstream out ("buline.out");
int n, c, maxi, pf, lf;
int arr[400004], s[400004], p[400004], l[400004];
/*
S[I] = SUBSECVENTA DE SUMA MAXIMA CE SE TERMINA PE POZ I
P[I] = POZITIA DE INCEPUT A SUBSECVENTEI DE SUMA MAXIMA CARE SE TERMINA PE POZ I
L[I] = LUNGIMEA SUBSECVENTEI DE SUMA MAXIMA CARE SE TERMINA PE POZ I
*/
int main()
{
in>>n;
for( int i = 1; i <= n; i++ )
{
in>>arr[i]>>c;
arr[i] = ( c == 0 )? -arr[i] : arr[i];
}
for( int i = 1; i <= n-1; i++ )
arr[i + n] = arr[i];
s[1] = arr[1];
l[1] = 1;
p[1] = 1;
for( int i = 2; i <= 2*n - 1; i++ )
if( s[i-1] + arr[i] > arr[i] )
{
s[i] = s[i-1] + arr[i];
p[i] = p[i-1];
l[i] = l[i-1] + 1;
}
else
{
s[i] = arr[i];
p[i] = i;
l[i] = 1;
}
maxi = -0x7fffffff;
for( int i = 1; i <= 2*n - 1; i++ )
if( maxi < s[i] )
{
maxi = s[i];
pf = p[i];
lf = l[i];
}
out<<maxi<<" "<<pf<<" "<<lf;
return 0;
}