Pagini recente » Cod sursa (job #1054724) | Cod sursa (job #1444577) | Cod sursa (job #2828683) | Cod sursa (job #503925) | Cod sursa (job #213515)
Cod sursa(job #213515)
#include <stdio.h>
#define MAXN 200001
struct sume
{
int s;//suma optima pana la pozitia i
int p;//pozitia la care se afla ultimul element din s
};
int n, p, l, max, v [MAXN], s [MAXN];
sume t [MAXN];
void scan ()
{
int i, tip;
scanf ("%d", &n);
scanf ("%d%d", v+1, &tip);
if (tip == 0)
v [1]*=(-1);
s [1]=v [1];
t [1].s=v [1];
t [1].p=1;
for (i=2; i<=n; ++i)
{
scanf ("%d%d", v+i, &tip);
if (tip == 0)
v [i]*=(-1);
s [i]=s [i-1]+v [i];
if (s [i] > t [i-1].s)
{
t [i].s=s [i];
t [i].p=i;
}
else
{
t [i].s=t [i-1].s;
t [i].p=t [i-1].p;
}
}
}
void sum1 ()
{
int sc=0, i, poz=1;
for (i=1; i<=n; ++i)
{
sc+=v [i];
if (sc > max)
{
max=sc;
p=poz;
l=i-poz+1;
}
if (sc < 0)
{
poz=i+1;
sc=0;
}
}
}
void sum2 ()
{
int i, x;
for (i=1; i<=n; ++i)
{
x=t [i-1].s+s [n]-s [i-1];
if (max < x)
{
max=x;
p=i;
l=n-i+1+t [i-1].p;
}
}
}
int main ()
{
freopen ("buline.in", "r", stdin);
freopen ("buline.out", "w", stdout);
scan ();
sum1 ();//sumele posibile daca nu sunt sub forma de cerc
sum2 ();
printf ("%d %d %d\n", max, p, l);
return 0;
}