Pagini recente » Cod sursa (job #2985922) | Cod sursa (job #806132) | Cod sursa (job #523272) | Cod sursa (job #980630) | Cod sursa (job #276363)
Cod sursa(job #276363)
#include <stdio.h>
#define DIM 200001
long int v[DIM];
long int x[DIM];
long int n,i,iMin,iMax,iMin1,iMax1,max,s,sum1,sum2,sTot,iMin2,iMax2;
int t;
int main(){
FILE *f = fopen("buline.in","r");
fscanf(f,"%ld",&n);
for (i=1;i<=n;i++) {
fscanf(f,"%ld %d",&v[i],&t);
if (t==0) {
v[i]=-v[i];
}
}
fclose(f);
//secventa de suma maxima
x[1]=v[1];
for (i=2;i<=n;i++)
if (x[i-1]+v[i]>v[i])
x[i]=x[i-1]+v[i];
else
x[i]=v[i];
iMax = 1;
max = x[1];
for (i=2;i<=n;i++)
if (x[i]>max) {
max = x[i];
iMax = i;
}
s=0;
for (iMin=iMax;iMin>=1;iMin--) {
s+=v[iMin];
if (s==max)
break;
}
sum1=s;
iMin1 = iMin;
iMax1 = iMax;
//secventa de suma minima
x[1]=1;
for (i=2;i<=n;i++)
if (x[i-1]+v[i]<v[i])
x[i]=x[i-1]+v[i];
else
x[i]=v[i];
iMax = 1;
max = x[1];
for (i=2;i<=n;i++)
if (x[i]<max) {
max = x[i];
iMax = i;
}
s=0;
for (iMin=iMax;iMin>=1;iMin--) {
s+=v[iMin];
if (s==max)
break;
}
iMin2 = iMin;
iMax2 = iMax;
sum2=s;
sTot = 0;
for (i=1;i<=n;i++)
sTot+=v[i];
FILE *g = fopen("buline.out","w");
if (sum1>sTot-sum2) {
fprintf(g,"%ld %ld %ld",sum1,iMin1,iMax1-iMin1+1);
} else {
fprintf(g,"%ld %ld %ld",sTot-sum2,iMax2+1,n-(iMax2-iMin2+1));
}
fclose(g);
return 0;
}