Cod sursa(job #1316627)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 13 ianuarie 2015 22:53:34
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.31 kb
#include <stdio.h>
#define DIM 10000
FILE *fin,*fout;
char buff[DIM];
int poz=0;
void citeste(long long &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,fin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,fin),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}
long long int a[50001],x[50001],y[50001],maxim[50001];
int main()
{
    fin=fopen("secv2.in","r");
    fout=fopen("secv2.out","w");
    long long n,k;
    fscanf(fin,"%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%lld",&a[i]);
        maxim[i]=-12000000000;
    }
    long long rasp=-12000000000,rasx,rasy;
    maxim[k]=a[1];
    for(int i=2;i<=k;i++)
    {
        maxim[k]+=a[i];
    }
    x[k]=1;
    y[k]=k;
    for(int i=k+1;i<=n;i++)
    {
        if(y[i-1]-x[i-1]+1>=k)
        {
            if(a[x[i-1]]<=0)
            {
                if(a[i]>a[x[i-1]])
                {
                    maxim[i]=maxim[i-1]+a[i]-a[x[i-1]];
                    x[i]=x[i-1]+1;
                    y[i]=i;
                }
                else
                {
                    maxim[i]=a[i];
                    x[i]=i;
                    y[i]=i;
                }
            }
            else
            {
                if(a[i]>=0)
                {
                    maxim[i]=a[i]+maxim[i-1];
                    x[i]=x[i-1];
                    y[i]=i;
                }
            }
        }
        else
        {
            if(maxim[i-1]>=0)
            {
                x[i]=x[i-1];
                y[i]=i;
                maxim[i]=a[i]+maxim[i-1];
            }
            else
            {
                maxim[i]=a[i];
                x[i]=i;
                y[i]=i;
            }
        }
    }
    for(int i=k;i<=n;i++)
    {
        if(rasp<maxim[i]&&y[i]-x[i]+1>=k)
        {
            rasp=maxim[i];
            rasx=x[i];
            rasy=y[i];
        }
    }
    fprintf(fout,"%lld %lld %lld\n",rasx,rasy,rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}