Pagini recente » Cod sursa (job #3252042) | Cod sursa (job #919258) | Cod sursa (job #52993) | Cod sursa (job #817613) | Cod sursa (job #1522500)
#include <cstdio>
#include <algorithm>
#include <deque>
#include <climits>
#define maxN 400005
using namespace std;
int n, i, j, sol=-INT_MAX, v[maxN], cl, fin, p, s[maxN];
deque <int> q;
int semn[] = {-1, 1};
int main()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
scanf("%d %d", &v[i], &cl);
v[i] *= semn[cl];
}
p = 0;
for(i = 1; i < n; i++)
v[n + i] = v[i];
q.push_front(0);
for(i = 1; i <= 2 * n-1; i++)
{
s[i] = s[i-1] + v[i];
while(!q.empty() && s[q.back()]>s[i])
q.pop_back();
q.push_back(i);
if(i - n == q.front()) q.pop_front();
if(s[q.front()] > 0)
if(s[i] > sol && i <= n)
{
sol = s[i], p = 1, fin = i;
}
if(s[i] - s[q.front()] > sol)
sol = s[i]-s[q.front()], p = q.front()+1, fin = i-q.front();
}
printf("%d %d %d", sol, p, fin);
return 0;
}