# Cod sursa(job #30367)

Utilizator Data 13 martie 2007 20:30:12 Buline 100 cpp done Arhiva de probleme 1.64 kb
``````#include <cstdio>

#define inf 2000000001
#define Nmax 200005

int n, v[Nmax];
int best = -inf, start, lung;

{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);

int i, val, semn;

scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d %d", &val, &semn);
if (semn) v[i] = val;
else v[i] = -val;
}
}

void solve()
{
int i, sum = 0, min = 0, poz = n+1, S = 0;
int best2 = -inf, start2, lung2;

//solutia nu este circulara
for (i = n; i; --i)
{
sum += v[i];
if (sum - min >= best)
{
best = sum - min;
start = i;
lung = poz - i;
}
if (sum <= min)
{
min = sum;
poz = i;
}
}

//solutia este circulara
for (i = 1; i <= n; ++i)
S += v[i], v[i] = -v[i];

min = 0, poz = 0;
sum = 0;

for (i = 1; i < n; ++i)
{
sum += v[i];
if (sum - min > best2)
{
best2 = sum - min;
start2 = i+1;
lung2 = n - (i - poz);
}
if (sum < min)
{
min = sum;
poz = i;
}
}

best2 = S+best2;

if ((best2 > best) || (best2 == best && start2 < start) || (best2 == best && start2 == start && lung2 < lung))
{
best = best2;
start = start2;
lung = lung2;
}
printf("%d %d %d\n", best, start, lung);
}

int main()
{