Pagini recente » Cod sursa (job #330562) | Cod sursa (job #2909819) | Cod sursa (job #1492700) | Cod sursa (job #1232323) | Cod sursa (job #1011368)
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int v[400001], s[400001], d[400001],i,j,n,a,b,sum,p,u,pc,dc,pmax,dmax,maxim;
int main () {
fin>>n;
for (i=1;i<=n;i++) {
fin>>a>>b;
if (b==0)
v[i]=v[i+n]=a * (-1);
else
v[i]=v[i+n]=a;
}
for (i=1;i<=n+n;i++){
s[i]= s[i-1] +v[i];
}
p=1;
d[++u]=0;
for (i=1;i<=n+n;i++) {
sum= s[i]-s[d[p]];
pc=d[p]+1;
dc=i-d[p];
if ((sum>maxim)||(sum==maxim && pc< pmax) || (sum==maxim && pc==pmax && dc < dmax) ){
maxim=sum;
pmax=pc;
dmax=dc;
}
while (p <= u && s[i] <= s[d[u]])
u --;
d[++u] = i;
if (d[p]+n == i)
p++;
}
fout <<maxim<<" "<<pmax<<" "<<dmax<<"\n";
return 0;
}