Cod sursa(job #1622026)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 1 martie 2016 00:09:04
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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];
priority_queue <pair <int, int> > PQ;
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] = DPT[k];
    for(i=k+1; i<=n; i++){
        PQ.push(make_pair(DPT[i - k], i - k));
        if(PQ.top().first > 0){
            sumak = S[i] - S[PQ.top().second];
            DP[i] = PQ.top().first + sumak;
            STR[i] = ST[PQ.top().second];
        }
        else{
            sumak = S[i] - S[i - k];
            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;
}