Cod sursa(job #2166143)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 13 martie 2018 15:44:12
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[50005],sum[50005],l[50005];

int main()
{
    int n,k,Max=-100000000,st,dr;
    in >> n >> k;
    for (int i = 1; i<=n; i++)
        in >> v[i];
    sum[1] = Max = v[1];
    l[1] = 1;
    bool ok = 0;
    for (int i = 2; i<=n; i++)
    {
        if (v[i]+sum[i-1]>v[i])
        {
            sum[i] = v[i]+sum[i-1];
            l[i] = 1+l[i-1];
        }
        else
        {
            sum[i] = v[i];
            l[i] = 1;
        }
        if (l[i]>=k && sum[i]>Max)
        {
            Max = sum[i];
            st = i-l[i]+1;
            dr = i;
            ok = 1;
        }
    }
    if (ok)
    {
        out << st << " " << dr << " " << Max;
    }
    else
    {
        memset(sum,0,sizeof(sum));
        for (int i = 1; i<=n; i++)
            sum[i] = sum[i-1]+v[i];
        for (int i = k; i<=n; i++)
            if (sum[i]-sum[i-k+1]>Max)
            {
                Max = sum[i]-sum[i-k+1];
                st = i-k+1;
                dr = i;
            }
        out << st << " " << dr << " " << Max;
    }
}