Cod sursa(job #1127903)

Utilizator alex_d01Alex Silviu alex_d01 Data 27 februarie 2014 14:16:29
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <iostream>

#define NMax 50005
#define MIN_INF -1<<31

using namespace std;

ifstream f("secv2.in");
ofstream g("secv2.out");

int a[NMax],dk[NMax],n,k,i,j;
long maxim,sfmax,lmax,ts,stmax,sfmax2,bigmax;

void afisare()
{
    g<<stmax<<' '<<sfmax<<' '<<bigmax<<'\n';
}

void programareDinamica()
{
    i=k;

    for (j=i;j>=1;j--)
      dk[i]+=a[j];

    for (i=k+1;i<=n;i++)
      dk[i]=dk[i-1]-a[i-k]+a[i];

    maxim=MIN_INF;
    for (i=k;i<=n;i++)
        if (dk[i]>maxim)
        {   maxim=dk[i];
            sfmax=i;
        }

    dk[sfmax-k]=a[sfmax-k];
    for (i=sfmax-k-1;i>=1;i--)
        dk[i]=a[i]+dk[i+1];

    maxim=MIN_INF;
    for (i=1;i<=sfmax-k;i++)
        if (dk[i]>maxim)
        {
            maxim=dk[i];
            stmax=i;
        }

    if (maxim<0)
        stmax=sfmax-k+1;
    dk[sfmax+1]=a[sfmax+1];

    for (i=sfmax+2;i<=n;i++)
        dk[i]=a[i]+dk[i-1];

    maxim=MIN_INF;
    for (i=sfmax+1;i<=n;i++)
        if (dk[i]>maxim)
        {
            maxim=dk[i];
            sfmax2=i;
        }
    if (maxim>0)
      sfmax=sfmax2;
    bigmax=0;
    for (i=stmax;i<=sfmax;i++)
      bigmax+=a[i];
}

void citire()
{
    f>>n>>k;
    for (i=1;i<=n;i++)
      f>>a[i];
}

int main()
{
    citire();
    programareDinamica();
    afisare();

    return 0;
}