Cod sursa(job #1096459)

Utilizator IronWingVlad Paunescu IronWing Data 2 februarie 2014 03:16:08
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
/* 
 * File:   secventa.cpp
 * Author: Vlad
 *
 * Created on January 31, 2014, 2:05 AM
 */

#include <fstream>

using namespace std;


const int MAX_N = 50002;
int n, k;
int a[MAX_N], s[MAX_N], minS[MAX_N];


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

int main(int argc, char** argv) {

    f >> n >> k;
    for (int i = 1; i <= n; i++) {
        f >> a[i];
    }

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

    // Si - Min(Sj), j < i.
    // compute min[i], minimum of sum ending in i
    minS[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[minS[i - 1]] > s[i]) {
            minS[i] = i;
        } else minS[i] = minS[i - 1];
    }
    int maxLeft = 1, maxRight = n, maxSum = s[n];
    for (int i = k; i <= n; i++) {
        if (s[i] - s[minS[i - k]] > maxSum) {
            maxSum = s[i] - s[minS[i - k]];
            maxLeft = minS[i - k] + 1;
            maxRight = i;
        }
    }

    g << maxLeft << ' ' << maxRight << ' ' << maxSum << '\n';


    return 0;
}