Cod sursa(job #1896148)

Utilizator RaresEGaySopterean Adrian RaresEGay Data 28 februarie 2017 14:53:06
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <iostream>
#define maxn 50001
#define INF 0x3f3f3f3f
using namespace std;

int n, k, s[maxn];
int maxim = -INF, l, r, minim[maxn], position[maxn];

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

int main(){
    f >> n >> k;

    for(int i = 1; i <= n; ++i){
        f >> s[i];
        s[i] += s[i-1];

        if(s[i] < minim[i-1]){
            minim[i] = s[i];
            position[i] = i;
        }
        else{
            minim[i] = minim[i-1];
            position[i] = position[i-1];
        }
        if(i >= k && s[i] - minim[i-k] > maxim){
            maxim = s[i] - minim[i-k];
            l = position[i-k] + 1;
            r = i;
        }
    }

    g << l << ' ' << r << ' ' << maxim << '\n';
}