Pagini recente » Cod sursa (job #37244) | Cod sursa (job #1115885) | Cod sursa (job #1462500) | Cod sursa (job #1075589) | Cod sursa (job #30367)
Cod sursa(job #30367)
#include <cstdio>
#define inf 2000000001
#define Nmax 200005
int n, v[Nmax];
int best = -inf, start, lung;
void readdata()
{
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()
{
readdata();
solve();
return 0;
}