Pagini recente » Cod sursa (job #1117113) | Cod sursa (job #542739) | Cod sursa (job #1854616) | Cod sursa (job #2336505) | Cod sursa (job #2221950)
#include<fstream>
#include<algorithm>
#define DN 200005
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
long long n,s[DN],dp[DN],a[DN],f,rez,sum,poz,l,b[DN],c[DN];
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a[i];
fin>>f;
if(f==0)
a[i]=-a[i];
}
s[1]=dp[1]=a[1];
b[1]=1;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1]+a[i];
if(s[i-1]+a[i]>a[i])
{
s[i]=s[i-1]+a[i];
b[i]=b[i-1];
}
else
{
s[i]=a[i];
b[i]=i;
}
if(s[i]>rez)
{
rez=s[i];
poz=b[i];
l=i-b[i]+1;
}
}
c[1]=1;
for(int i=2;i<=n;i++)
{
if(dp[i-1]>dp[i])
{
dp[i]=dp[i-1];
c[i]=c[i-1];
}
else
c[i]=i;
}
for(int i=n;i>1;i--)
{
sum+=a[i];
if(sum+dp[i-1]>rez)
{
rez=sum+dp[i-1];
l=c[i-1]+n-i+1;
poz=i;
}
}
fout<<rez<<' '<<poz<<' '<<l;
}