Cod sursa(job #1742990)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 17 august 2016 13:55:02
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>
#include <math.h>
#include <algorithm>

using namespace std;

long long dp[50005];

int main(){
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);
    int k,n,i,j,x,id,jd;
    long long mx,mn;
    mx = -1e16;
    mn = 1e16;
    scanf("%d %d", &n, &k);
    for(i = 1;i <= n;i++){
        scanf("%d", &x);
        dp[i] = dp[i-1]+x;
    }
    for(i = k, j = 0;i <= n;i++, j++){
        if(dp[j] < mn){
            mn = dp[j];
            id = j+1;
        }
        if(dp[i] - mn > mx){
            mx = dp[i] - mn;
            jd = i;
        }
    }
    printf("%d %d %d", id, jd, mx);
}