Pagini recente » Cod sursa (job #1366003) | Cod sursa (job #2059830) | Cod sursa (job #2355645) | Cod sursa (job #2487770) | Cod sursa (job #393334)
Cod sursa(job #393334)
# include <fstream>
using namespace std;
int v[400003], n, sol=-1000000000;
void read ()
{
ifstream fin ("buline.in");
fin>>n;
int nrb, c;
for (int i=1;i<=n;i++)
{
fin>>nrb>>c;
if (c==1) v[i]=nrb;
else v[i]=-nrb;
v[n+i]=v[i];
}
}
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;
}
int main ()
{
read ();
ssm ();
return 0;
}