Pagini recente » Cod sursa (job #2356387) | Cod sursa (job #1718873) | Cod sursa (job #1471956) | Cod sursa (job #1659281) | Cod sursa (job #2130652)
#include <fstream>
#define INF 2000000000
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,p,a[400005],x,mx,x1,q,mn,p1,last,pi;
bool b;
void Operation(int poz)
{int i;
mn=1;x1=0;p1=last;
for(i=last+1;i<=poz;i++)
{x1+=a[i];
if(x1<mn){mn=x1;p1=i;}
}
}
int main()
{int i;
fin>>n;
for(i=1;i<=n;i++)
{fin>>x>>b;
if(b==1)a[i]=x;
else a[i]=-x;
}
for(i=n+1;i<=2*n;i++)
a[i]=a[i-n];
mx=a[1];
x=0;
last=1;
for(i=1;i<=2*n;i++)
{if(i-last>=n){Operation(i);x-=a[last];if(mn<1){last=p1+1;x+=-mn;//fout<<"(("<<last<<"))";
}
}
if(x+a[i]<=0){x=0;last=i+1;}
else {x=x+a[i];
if(x>mx){mx=x;p=i;pi=last;}
}
//fout<<i<<" "<<last<<"\n";
}
fout<<mx<<" "<<pi<<" "<<p-pi+1;
}