Pagini recente » Cod sursa (job #3236876) | Cod sursa (job #675830) | Cod sursa (job #754115) | Cod sursa (job #1451172) | Cod sursa (job #425413)
Cod sursa(job #425413)
#include<cstdio>
#include<fstream>
#include<vector>
#define pb push_back
#define INFI 2100000000
#define maxn 400005
using namespace std;
int n, smax, sum, ind, st, dr, v[maxn], presum, preind;
int main()
{
int i, x;
ifstream fin("buline.in");
freopen("buline.out", "w", stdout);
fin>>n;
for(i=1;i<=n;++i)
{
int temp;
fin>>x>>temp;
if(temp==0)
v[i]=-x;
else
v[i]=x;
}
for(i=n+1;i<=2*n;++i)
v[i]=v[i-n];
st=dr=ind=1;
smax=-INFI;
sum=v[1];
for(i=2;i<=2*n;++i)
{
if(sum+v[i]<v[i])
sum=v[i], ind=i, presum=0, preind=ind+1;
else
{
if(presum+v[i]<v[i])
presum=v[i], preind=i;
else
presum+=v[i];
if(i-ind==n)
{
sum=presum;
ind=preind;
preind=i+1;
presum=0;
/*
if(v[ind]<v[i])
sum-=v[ind], sum+=v[i], ind++;
else
{
ind++;
sum=v[ind];
i=ind;
}*/
}
else
{
sum+=v[i];
}
}
if(sum>smax)
smax=sum, st=ind, dr=i;
}
printf("%d %d %d", smax, st, dr-st+1);
return 0;
}