Cod sursa(job #1622088)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 1 martie 2016 01:15:50
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>

using namespace std;

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

int V[50005], DP[50005], ST[50005], DPT[50005], STR[50005], S[50005];
int n, k;
int const oo = 2000000000;

void citire()
{
    int i;

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

void rez()
{
    int i, maxi = -oo, ind, sumak;

    for(i=1; i<=n; i++){
        S[i] = S[i-1] + V[i];
        if(DPT[i-1] > 0){
            DPT[i] = DPT[i-1] + V[i];
            ST[i] = ST[i-1];
        }
        else{
            DPT[i] = V[i];
            ST[i] = i;
        }
    }

    DP[k] = S[k];
    STR[k] = 1;
    for(i=k+1; i<=n; i++){
        sumak = S[i] - S[i - k];
        if(DPT[i - k] > 0){
            DP[i] = DPT[i-k] + sumak;
            STR[i] = ST[i-k];
        }
        else{
            DP[i] = sumak;
            STR[i] = i - k + 1;
        }
    }

    for(i = k; i<=n; i++)
        if(DP[i] > maxi){
            maxi = DP[i];
            ind = i;
        }

    g<<STR[ind]<<" "<<ind<<" "<<maxi<<"\n";
}

int main()
{
    citire();
    rez();
    return 0;
}