Pagini recente » Istoria paginii runda/abcdefghijklmnopqrstuvwxyz | Istoria paginii runda/preoji_4/clasament | Cod sursa (job #1392161) | Istoria paginii runda/rar11/clasament | Cod sursa (job #2470877)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,b,w,poz,pozm,lm,l,v[400002];
long long smax,sum,best[400002],a[400002];
int main()
{
fin>>n;
for(i=1; i<=n; i++)
{
fin>>w>>b;
if(b==0)
{
v[i]=-w;
}
else v[i]=w;
sum+=v[i];
}
smax=v[1];
poz=1;
l=1;
for(i=1; i<=n; i++)
{
best[i]=v[i];
if(best[i]<best[i-1]+v[i])
{
best[i]=best[i-1]+v[i];
l++;
}
else
{
poz=i;
l=1;
}
if(smax<best[i]) smax=best[i],pozm=poz,lm=l;
}
a[1]=v[1];
for(i=2; i<=n; i++)
{
if(a[i-1]+v[i]<v[i]) a[i]=a[i-1]+v[i],l++;
else
{
a[i]=v[i];
l=1;
poz=i;
}
if(sum-a[i]>smax)
{
smax=sum-a[i];
if(i==n) pozm=1;
else pozm=i+1;
lm=n-l;
}
}
fout<<smax<<" "<<pozm<<" "<<lm;
return 0;
}