Cod sursa(job #2244725)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 23 septembrie 2018 15:30:10
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int ras,st=1,sf;
int v[500012],dp[500012];
int n,k;
int main()
{
    f>>n>>k;
    sf=k;
    for(int i=1;i<=n;++i)
    {
        f>>v[i];
        v[i]+=v[i-1];
    }
    for(int i=1;i<=n;++i)
    {
        dp[i]=v[i]-v[max(i-k,0)];
    }
    ras=dp[k];
    int stt=0;
    for(int i=k+1;i<=n;++i)
    {

        if(v[i]-v[i-1]+dp[i-1]<dp[i])
            stt=i-k+1;
        else
            dp[i]=v[i]-v[i-1]+dp[i-1];
        if(dp[i]>ras)
        {
            ras=dp[i];
            st=stt;
            sf=i;
        }
    }
    g<<st<<' '<<sf<<' '<<ras;
}