Pagini recente » Cod sursa (job #707570) | Cod sursa (job #1640555) | Cod sursa (job #1354891) | Cod sursa (job #1695845) | Cod sursa (job #843886)
Cod sursa(job #843886)
#include <cstdio>
using namespace std;
const int maxn = 200002;
int v[maxn];
long long S = 0;
int main()
{
int n,i;
int cr_max,cr_high_start,cr_high_end;
int cr_min,cr_low_start,cr_low_end;
int show_max,show_high_start,show_high_end;
int show_min,show_low_start,show_low_end;
bool semn;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d\n",&n);
const int N = n;
i = 1;
while(i<=N)
{
semn = 0;
scanf("%d %d",&v[i],&semn);
if(!semn)
v[i]= -v[i] ;
S+=v[i];
i ++;
}
cr_max = -(1<<30);
cr_min = 1<<30;
show_max = cr_max;
show_min = cr_min;
for(i=1;i<=N;++i)
{
if(cr_max >= 0)
{
cr_max += v[i];
cr_high_end = i;
}
else
{
cr_max = v[i];
cr_high_start = i;
cr_high_end = i;
}
if(cr_max > show_max)
{
show_max = cr_max;
show_high_start = cr_high_start;
show_high_end = cr_high_end;
}
if(cr_min <= 0)
{
cr_min += v[i];
cr_low_end = i;
}
else
{
cr_min = v[i];
cr_low_start=i;
cr_low_end=i;
}
if(cr_min < show_min)
{
show_min = cr_min;
show_low_end = cr_low_end;
show_low_start = cr_low_start;
}
}
if(S-show_min > show_max)
{
show_max = S-show_min;
show_high_start = show_low_end+1;
show_high_end = show_low_start + N - show_low_end-1;
}
else
{
show_high_end -= show_high_start;
++show_high_end;
}
printf("%d %d %d\n",show_max,show_high_start,show_high_end);
return 0;
}