Pagini recente » Cod sursa (job #2139302) | Cod sursa (job #1717942) | Cod sursa (job #2051529) | Cod sursa (job #1303126) | Cod sursa (job #72467)
Cod sursa(job #72467)
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#define max 200001
int n, a[max], s[max], t[max], tt[max];
void citire()
{
freopen("buline.in","r",stdin);
scanf("%d", &n);
int aux;
for (int i=1; i<=n; i++)
{
scanf("%d %d", &a[i], &aux);
if (aux == 0) a[i]*=-1;
}
fclose(stdin);
}
inline int MAX( int a, int b)
{
if (a>b) return a;
else return b;
}
void solve()
{
t[1]=s[1]=a[1];
for (int i = 2; i<=n; i++)
s[i] =s[i-1] + a[i];
tt[1]=1;
for ( int i =2; i<=n; i++)
{
t[i] = MAX( t[i-1], s[i] );
if (t[i] == t[i-1] ) tt[i] = tt[i-1];
else tt[i] = i;
}
int rez=-MAXINT, pstart, lung;
for (int i = 2; i<=n; i++)
{
// rez = MAX ( t[i-1] + s[n]-s[i-1], rez);
if (t[i-1] + s[n]-s[i-1] > rez )
{
rez = t[i-1] + s[n]-s[i-1];
pstart = i;
lung = n-i+1 + tt[i-1];
//pstop = tt[i-1];
}
}
int s=0,start=1;
for (int i =1; i<=n; i++)
{
//s = MAX( s+a[i], a[i]);
//rez = MAX( rez, s);
if (s+a[i] > a[i])
s=s+a[i];
else
{
s=a[i];
start=i;
}
if (s> rez)
{
rez=s; pstart=start; lung = i-start+1;
}
}
freopen("buline.out", "w", stdout);
printf("%d %d %d", rez, pstart, lung);
fclose(stdout);
}
int main()
{
citire();
solve();
return 0;
}