Cod sursa(job #1374420)

Utilizator retrogradLucian Bicsi retrograd Data 5 martie 2015 09:09:55
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<vector>

using namespace std;
typedef int var;

ifstream fin("secv2.in");
ofstream fout("secv2.out");

#define MAXN 500002
#define INF (1 << 29)

var V[MAXN], S[MAXN], BEST[MAXN], B[MAXN];
var n, k, sum, bun = -INF;
var bestb, beste;

int main() {
    fin>>n>>k;
    for(var i=1; i<=n; i++) {
        fin>>V[i];
    }
    for(var i=1; i<=k; i++) {
        sum +=V[i];
        BEST[i] = -INF;
    }
    for(var i=k; i<=n; i++) {
        S[i] = sum;

        if(S[i] > V[i] + BEST[i-1]) {
            B[i] = i-k+1;
            BEST[i] = S[i];
        } else {
            BEST[i] = V[i] + BEST[i-1];
            B[i] = B[i-1];
        }
        if(bun < BEST[i]) {
            bun = BEST[i];
            bestb = B[i];
            beste = i;
        }

        sum -= V[i-k+1];
        sum += V[i+1];
    }
    fout<<bestb<<" "<<beste<<" "<<bun;

    return 0;
}