Pagini recente » Cod sursa (job #3237120) | Cod sursa (job #268675) | Cod sursa (job #485781) | Cod sursa (job #1656326) | Cod sursa (job #2931553)
#include <fstream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
int n,i,val,v[400100],st[400100],sum[400100],s[400100],sumax[400100],Lsol,isol,sol;
int main () {
fin>>n;
for (i=1;i<=n;i++) {
fin>>v[i]>>val;
if (val==0) {
v[i]=-v[i];
}
if (s[i-1]+v[i]>v[i]) {
s[i]=s[i-1]+v[i];
st[i]=st[i-1];
}
else {
s[i]=v[i];
st[i]=i;
}
if (s[i]>sol) {
sol=s[i];
isol=st[i];
Lsol=i-st[i]+1;
}
}
sum[1]=v[1];
sumax[1]=v[1];
for (i=2;i<=n;i++) {
sum[i]=sum[i-1]+v[i];
sumax[i]=max(sumax[i-1],sum[i]);
if (sumax[i-1]>sum[i]) {
sumax[i]=sumax[i-1];
st[i]=st[i-1];
}
else {
sumax[i]=sum[i];
st[i]=i;
}
}
for (i=1;i<=n;i++) {
if (sol<sumax[i-1]-sum[n]+sum[i-1]) {
sol=sumax[i-1]-sum[n]+sum[i-1];
isol=i;
Lsol=st[i-1]+n-i+1;
}
}
fout<<sol<<" "<<isol<<" "<<Lsol;
}