Cod sursa(job #1274473)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 23 noiembrie 2014 21:28:07
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMax = 50010;
long long s[NMax],v[NMax];
int main()
{
    long long som = 0,bsom = 0;
    int N,K,pi,bpi,pf,bpf;
    f >> N >> K;
    for(int i = 1; i <= K; i++){
        f >> v[i];
        som += v[i];
    }
    s[K] = som;
    for(int i = K + 1; i <= N; i++){
        f >> v[i];
        s[i] = s[i-1] + v[i] - v[i-K];
    }
    //for(int i = 1; i <= N; i++)
     //   g << s[i] << " ";
    som = 0;
    bpi = bpf = pi = K;
    bsom = s[K];
    for(int i = K + 1; i <= N; i++){
        som = s[i];
        s[i] = max(s[i-1] + v[i], som);
        if(som == s[i] && s[i] >= 0){
            pi = i;
            pf = i;
        }
        if(som >= 0)
            pf = i;
        else
            pf = i - 1;
        if(s[i] > bsom){
            bpi = pi;
            bpf = pf;
            bsom = s[i];
        }
        if(som < 0)
            pi = i + 1;
    }
    g << bpi - K + 1 << " " << bpf << " " << bsom;
    return 0;
}