Pagini recente » Cod sursa (job #1289070) | Cod sursa (job #650985) | Cod sursa (job #1052005) | Cod sursa (job #72142) | Cod sursa (job #1723834)
#include <cstdio>
#include<deque>
#define MAXN 200000
using namespace std;
int v[2*MAXN+1];
long long s[2*MAXN+1];
deque<int>dq;
int main()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
int n, posmax, lmax, t;
long long maxs;
scanf("%d", &n);
for(int i=1;i<=n;++i)
{
scanf("%d%d", &v[i], &t);
if(!t) v[i]*=-1;
v[i+n]=v[i];
}
for(int i=1;i<=n*2;++i)
s[i]=s[i-1]+v[i];
maxs=s[1];
posmax=lmax=1;
dq.push_back(1);
for(int i=2;i<2*n;++i)
{
if(dq.front() < i-n)
dq.pop_front();
if(s[i]-s[dq.front()] > maxs)
{
maxs=s[i]-s[dq.front()];
posmax=dq.front() + 1;
lmax=i-dq.front();
}
while(!dq.empty() && s[i] < s[dq.back()])
dq.pop_back();
dq.push_back(i);
}
printf("%lld %d %d",maxs, posmax, lmax);
return 0;
}