Pagini recente » Cod sursa (job #622677) | Cod sursa (job #1070631) | Cod sursa (job #1167772) | Cod sursa (job #3253916) | Cod sursa (job #393825)
Cod sursa(job #393825)
#include<fstream>
using namespace std;
int v[400005];
int n,nr;
long long sol=-1000000;
//void SSm(int st,int dr);
void ssm();
//ofstream fout("buline.out");
int main()
{
ifstream fin("buline.in");
//freopen("buline.out","w",stdout);
fin>>n;
int i;
for(i=1;i<=n;i++)
{
int a,b;
fin>>a>>b;
if(b==0)
v[++nr]=-a;
else
v[++nr]=a;
}
for(i=1;i<n;i++)
v[++nr]=v[i];
ssm();
return 0;
}
void ssm ()
{
int dq[200000], p[200000], st, dr;
int scur, smin, x, y;
scur=smin=v[1];
x=y=1;
st=dr=1;
dq[st]=smin;
p[st]=1;
for (int i=2;i<2*n;i++)
{
scur+=v[i];
if (scur-dq[st]>sol)
sol=scur-dq[st], x=p[st], y=i;
while (dr>=st && scur<dq[dr])dr--;
dq[++dr]=scur, p[dr]=i;
if (i-p[st]==n)
st++;
}
ofstream fout ("buline.out");
fout<<sol<<" "<<x+1<<" "<<y-x;
}