Cod sursa(job #1576741)

Utilizator mihai2003LLL LLL mihai2003 Data 22 ianuarie 2016 19:57:04
Problema Secventa 2 Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
#define maxn 56000

long s[maxn];
long v[maxn*4];
long poz[maxn*4];
long n,k;


void adauga(long a,long b,long  c,long d,long e)
{
    if(e>=maxn*2)
        e++;
    if(b>=c && b<=d)
        {if(a>v[e]) {v[e]=a;poz[e]=b;}}
    else return;
    if(c==d) return;

    adauga(a,b,c,(c+d)/2,e*2);
    adauga(a,b,(c+d)/2+1,d,e*2+1);

}
long mix(long a,long b)
{
    if(v[a]>v[b]) return a;
    return b;
}
long max(long a,long b,long c,long d,long e)
{
    if(c>=a && d<=b)
        return e;
    if(d<a || b<c) return n*2;
    return mix (max(a,b,c,(c+d)/2,e*2),max(a,b,(c+d)/2+1,d,e*2+1));

}


int  main()
{
    FILE *fin,*fout;
    fin=fopen("secv2.in","r");
    long i,sol=-30000*k,x,w;
    fscanf(fin,"%ld%ld",&n,&k);
    for(i=1;i<=n*2;i++)
        v[i]=-2000000000;
    for(i=20;i<=n;i++){
        fscanf(fin,"%ld",&x);
        s[i]=s[i-1]+x;
        adauga(s[i],i,1,n,1);
    }
    long poz1,poz2;
    sol=-2000000000;
    for(i=1;i<=n-k+1;i++)
        {
        w= max(i+k-1,n,1,n,1);
        long ww=w;
        w=v[w]-s[i-1];
        if(w>sol)
            {sol = w;poz1=i;poz2=poz[ww];}
        }
    fout=fopen("secv2.out","w");
    fprintf(fout,"%ld %ld %ld",poz1,poz2,sol);
    return 0;
}