Cod sursa(job #1236253)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 1 octombrie 2014 19:00:28
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>

#define Nmax 50005

using namespace std;
int N,K;
int v[Nmax];
int spart[Nmax];
int DP[Nmax];
struct poz{
    int a,b;
    poz(){
        a = b = 0;
    }
    poz(int a,int b){
        this->a = a;
        this->b = b;
    }
}p[Nmax];

int main()
{
    freopen("secv2.in","r",stdin);
    freopen("secv2.out","w",stdout);

    scanf("%d%d",&N,&K);
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d",&v[i]);
        spart[i] = spart[i-1] + v[i];
    }
    p[K] = poz(1,K);
    DP[K] = spart[K];
    int best = DP[K], besta = 1,bestb = K;
    for(int i = K + 1; i <= N; ++i)
    {
        if(spart[i] - spart[i-K] > DP[i-1] + v[i])
        {
            DP[i] = spart[i] - spart[i-K];
            p[i] = poz(i-K+1,i);
        }
        else
        {
            DP[i] = DP[i-1] + v[i];
            p[i] = p[i-1];
            p[i].b++;
        }
        if(DP[i] > best)
        {
            best = DP[i];
            besta = p[i].a;
            bestb = p[i].b;
        }
    }
    printf("%d %d %d\n",besta, bestb, best);

    return 0;
}