Cod sursa(job #1590346)

Utilizator antanaAntonia Boca antana Data 4 februarie 2016 22:03:39
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#define MAX 50000
using namespace std;
int v[MAX+1], best[MAX+1], poz1[MAX+1], s[MAX+1];
int main()
{
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);
    int n, k,  i, max, maxi, maxj;
    scanf("%d%d", &n, &k);
    for(i=1;i<=n;i++)
        scanf("%d", &v[i]);
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+v[i];
    max=s[k];
    poz1[k]=1;
    best[k]=s[k];
    for(i=k+1;i<=n;i++)
    {
        if(best[i-1]+v[i]>s[i]-s[i-k])
        {
            poz1[i]=poz1[i-1];
            best[i]=best[i-1]+v[i];
        }
        else
        {
            best[i]=s[i]-s[i-k];
            poz1[i]=i-k+1;
        }
        if(max<best[i])
        {
            max=best[i];
            maxi=poz1[i];
            maxj=i;
        }
    }
    printf("%d %d %d", maxi, maxj, max);
    return 0;
}