Pagini recente » Cod sursa (job #1498994) | Cod sursa (job #1122234) | Cod sursa (job #2444888) | Cod sursa (job #521395) | Cod sursa (job #2117155)
#include <bits/stdc++.h>
#define DIM 200005
using namespace std;
ifstream in ("buline.in");
ofstream out ("buline.out");
int n, culoare, sum;
int maxi, max_poz, max_l;
int mini, min_poz, min_l;
int v[DIM], subsec[DIM], l[DIM];
int main()
{
in>>n;
for( int i = 1; i <= n; i++ )
{
in>>v[i]>>culoare;
if( culoare == 0 )
v[i] = -v[i];
sum += v[i];
}
//SUBSEC DE SUMA MAXIMA
subsec[1] = v[1];
l[1] = 1;
for( int i = 2; i <= n; i++ )
if( subsec[i - 1] + v[i] >= v[i] )
{
subsec[i] = subsec[i - 1] + v[i];
l[i] = l[i - 1] + 1;
}
else
{
subsec[i] = v[i];
l[i] = 1;
}
maxi = subsec[1];
max_poz = 1;
max_l = 1;
for( int i = 2; i <= n; i++ )
if( maxi < subsec[i] )
{
maxi = subsec[i];
max_poz = i - l[i] + 1;
max_l = l[i];
}
//SUBSEC DE SUMA MINIMA
subsec[1] = v[1];
l[1] = 1;
for( int i = 2; i <= n; i++ )
if( subsec[i - 1] + v[i] <= v[i] )
{
subsec[i] = subsec[i - 1] + v[i];
l[i] = l[i - 1] + 1;
}
else
{
subsec[i] = v[i];
l[i] = 1;
}
mini = subsec[1];
min_poz = 1;
min_l = 1;
for( int i = 2; i <= n; i++ )
if( mini > subsec[i] )
{
mini = subsec[i];
min_poz = i - l[i] + 1;
min_l = l[i];
}
if( maxi > sum - mini )
out<<maxi<<" "<<max_poz<<" "<<max_l;
else
out<<sum - mini<<" "<<min_poz + 1<<" "<<n - min_l;
return 0;
}