Pagini recente » Cod sursa (job #2987457) | Cod sursa (job #2902288) | Cod sursa (job #3146291) | Cod sursa (job #3262921) | Cod sursa (job #3203172)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n, a[200001], sign, length;
int main()
{
fin>>n;
for(int i = 1; i <= n; ++i)
{
fin>>a[i]>>sign;
if(sign == 0)
a[i] *= (-1);
}
///Subsecventa de suma maxima
int i_start, i_end;
int current, maxi, imax, jmax;
current = maxi = a[1];
i_start = i_end = 1;
imax = jmax = 1;
for(int i = 2; i <= n; ++i)
{
if(current + a[i] >= a[i])
{
current += a[i];
i_end = i;
if(current > maxi)
maxi = current, imax = i_start, jmax = i_end;
else if(current == maxi)
{
if(i_start == imax)
jmax = min(jmax, i_end);
else if(i_start < imax)
imax = i_start, jmax = i_end;
}
}
else{
current = a[i];
i_start = i_end = i;
if(current > maxi)
maxi = current, imax = i_start, jmax = i_end;
}
}
///Subsecventa de suma minima
int mini, imin, jmin;
current = mini = a[1];
i_start = i_end = 1;
imin = jmin = 1;
for(int i = 2; i <= n; ++i)
{
if(current + a[i] < a[i])
{
current += a[i];
i_end = i;
if(current < mini)
mini = current, imin = i_start, jmin = i_end;
else if(current == mini)
{
if(i_end > jmin)
imin = i_start, jmin = i_end;
}
}
else{
current = a[i];
i_start = i_end = i;
if(current < mini)
mini = current, imin = jmin = i;
}
}
int sum_start = 0, sum_end = 0;
for(int i = 1; i < imin; ++i)
sum_start += a[i];
for(int i = jmin + 1; i <= n; ++i)
sum_end += a[i];
length = jmax - imax + 1;
if(sum_end + sum_start > maxi)
{
maxi = sum_end + sum_start;
imax = jmin+1, jmax = imin - 1;
length = imin - 1 + n - jmin;
}
else if(sum_end + sum_start == maxi)
{
if(imax > jmin+1)
imax = jmin+1, jmax = imin-1, length = imin - 1 + n - jmin;
else if(imax == jmin+1)
{
if(jmax - imax + 1 > n - jmin + imin - 1)
imax = jmin+1, jmax = imin-1, length = imin - 1 + n - jmin;
}
}
fout<<maxi<<' '<<imax<<' '<<length;
return 0;
}