Pagini recente » Cod sursa (job #2861696) | Cod sursa (job #1440636) | Cod sursa (job #2000776) | Cod sursa (job #1961386) | Cod sursa (job #26285)
Cod sursa(job #26285)
#include <stdio.h>
#define nmax 400001
int v[nmax], s[nmax], st[nmax], summax = - 10001, start, len, n, sum[nmax], t[nmax];
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
int i, a, b;
scanf("%d", &n);
for(i = 1; i <= n; ++i)
{
scanf("%d%d", &a, &b);
if(b == 0)
{
v[i] = -a;
}
else
{
v[i] = a;
}
v[n + i] = v[i];
if(s[i - 1] > 0)
{
s[i] = s[i - 1] + v[i];
st[i] = st[i - 1];
}
else
{
s[i] = v[i];
st[i] = i;
}
if(s[i] > summax || (s[i] == summax && st[i] < start) || (s[i] == summax && st[i] == start && i - st[i] + 1 < len))
{
summax = s[i];
start = st[i];
len = i - st[i] + 1;
}
sum[i] = sum[i - 1] + v[i];
if(sum[t[i - 1]] > sum[i])
{
t[i] = t[i - 1];
}
else
{
t[i] = i;
}
}
for(i = 2; i <= n; ++i)
{
if(sum[n] - sum[i - 1] + sum[t[i - 1]] > summax || (sum[n] - sum[i - 1] + sum[t[i - 1]] == summax && i < start) || (sum[n] - sum[i - 1] + sum[t[i - 1]] == summax && i == start && n - i + 1 + t[i - 1] < len))
{
summax = sum[n] - sum[i - 1] + sum[t[i - 1]];
start = i;
len = n - i + 1 + t[i - 1];
}
}
printf("%d %d %d\n", summax, start, len);
return 0;
}