Pagini recente » Cod sursa (job #478732) | Cod sursa (job #1473798) | Cod sursa (job #738154) | Cod sursa (job #1692860) | Cod sursa (job #72503)
Cod sursa(job #72503)
#include <cstdio>
using namespace std;
#define FIN "buline.in"
#define FOUT "buline.out"
#define MAX_N 200005
int N,i,a[MAX_N<<1];
int S[MAX_N];
int T[MAX_N];
int sc,smax;
int in,out,ina,in1;
int leng;
int s1,s2;
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d",&N);
for (i=1; i<=N; i++)
{
scanf("%d %d",&s1,&s2);
if (s2==1) { a[i]=s1; a[i+N]=s1; }
else { a[i]=-s1; a[i+N]=-s1; }
}
S[1]=a[1]; T[1]=a[1]; int max=-100000;
for (i=2; i<=N; i++)
{
S[i]=S[i-1]+a[i];
if (S[i]>max) max=S[i];
T[i]=max;
}
max=-100000;
for (i=1; i<=N; i++)
if (T[i-1]+S[N]-S[i-1]>max)
{ max=T[i-1]+S[N]-S[i-1]; in1=i; }
sc=0;
for (i=in1; i<=N*2; i++)
{ sc+=a[i]; if (sc==max) break; }
int lim=i;
// baga algoritm clasic
sc=smax=a[1];
in = 1; out = 1;
for (i=2; i<=N*2; i++)
{
if (sc<0 || i-ina>N)
{ sc=a[i]; ina=i; }
else sc+=a[i];
if (sc>smax)
{ smax=sc; in=ina; out=i; }
}
// baga maximul dintre cele 2
if (smax>max) printf("%d %d %d",smax,in,out-in+1);
else
printf("%d %d %d",max,in1,lim-in1+1);
fclose(stdin); fclose(stdout);
return 0;
}