Cod sursa(job #2759495)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 18 iunie 2021 14:17:23
Problema Secventa 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 50003;

int n,k,x,y;
ll hmax;
ll s[NMAX];

struct elem{
    ll sum,poz;
}dp[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++){
        int x;
        scanf("%d",&x);
        s[i]=s[i-1]+x;
        if(x + dp[i-1].sum > x){
            dp[i].sum = x + dp[i-1].sum;
            dp[i].poz=dp[i-1].poz;
        }else{
            dp[i].poz=i;
            dp[i].sum=x;
        }
    }
    for(int i=k;i<=n;i++){
        ll best = (s[i]-s[i-k]) + dp[i-k].sum;
        if(hmax < best){
            hmax = best;
            x=dp[i-k].poz;
            y=i;
        }
    }
    printf("%d %d %lli",x,y,hmax);

    return 0;
}