Pagini recente » Cod sursa (job #1172874) | Cod sursa (job #876952) | Cod sursa (job #2624856) | Cod sursa (job #2020846) | Cod sursa (job #877617)
Cod sursa(job #877617)
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int dmin[200002], dmax[20002], v[20002];
int n,i,maxim,minim,u1,p1,p2,u2,pmax,pmin,umax,umin,lg,s,a,b;
int main () {
fin>>n;
for (i=1;i<=n;i++) {
fin>>a>>b;
if (b==0)
v[i]=(a*-1);
else
v[i]=a;
}
dmax[1]=v[1];
dmin[1]=v[1];
maxim=dmax[1];
minim=dmin[1];
p1=1;u1=1;
p2=1;u2=1;
pmax=1;umax=1;
pmin=1;umin=1;
for (i=2;i<=n;i++) {
if (v[i] + dmax[i-1] >= v[i]) {
dmax[i] = v[i]+dmax[i-1];
} else {
dmax[i] = v[i];
p1 = i;
}
if (v[i]+dmin[i-1]< v[i])
dmin[i]=v[i]+dmin[i-1];
else {
dmin[i]=v[i];
p2=i;
}
if (dmax[i] > maxim) {
maxim = dmax[i];
pmax = p1;
umax = i;
} else
if (dmax[i] == maxim)
if (p1 == pmax && i<umax)
umax = i;
if (dmin[i]<minim){
minim=dmin[i];
pmin=p2;
umin=i;
}else
if (dmin[i]== minim)
if (i==umin && p2<pmin)
pmin= p2;
}
lg=umax-pmax+1;
for (i=umin+1;i<=n;i++)
s+=v[i];
for (i=1;i<pmin;i++)
s+=v[i];
if (s>maxim) {
maxim=s;
pmax=umin+1;
lg=n-(umin-pmin+1);
}else
if (s==maxim) {
if (umin<pmax) {
pmax=umin+1;
lg=n-(umin-pmin+1);
}
if (umin==pmax && n - (umin-pmin+1) < umax-pmax+1) {
pmax=umin+1;
lg=n-(umin-pmin+1);
}
}
fout << maxim<<" "<<pmax<<" "<<lg;
return 0;
}