Pagini recente » Cod sursa (job #650330) | Cod sursa (job #1433584) | Cod sursa (job #3271033) | Cod sursa (job #129309) | Cod sursa (job #793482)
Cod sursa(job #793482)
# include <cstdio>
using namespace std;
int n, i, val, op, maxim, st, dr, front, back, a[400005], s[400005], deque[400005];
int main()
{
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for (i = 1; i <= n; i++)
{
scanf("%d%d",&val,&op);
a[i] = (op ? val : - val);
a[i + n] = a[i];
}
for (i = 1; i <= 2 * n; i++)
s[i] = s[i - 1] + a[i];
maxim = s[n]; st = 1; dr = n; front = 1; back = 0;
for (i = 1; i <= 2 * n; i++)
{
while (front <= back && s[i] < s[deque[back]]) back--;
deque[++back] = i;
if (deque[front] == i - n) front++;
if (maxim < s[i] - s[deque[front]])
{
maxim = s[i] - s[deque[front]];
st = deque[front] + 1;
dr = i;
}
}
printf("%d %d %d", maxim, st, dr - st + 1);
return 0;
}