Cod sursa(job #1621981)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 29 februarie 2016 23:44:58
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 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];
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;

    for(i=1; i<=k-1; i++){
        if(DP[i-1] <= 0){
            DP[i] = V[i];
            ST[i] = i;
        }
        else{
            DP[i] = DP[i-1] + V[i];
            ST[i] = ST[i-1];
        }
    }

    for(i=k; i<=n; i++){
        PQ.push(make_pair(DP[i - k + 1], ST[i - k + 1]));
        if(PQ.top().first > 0){
            DP[i] = PQ.top().first + V[i];
            ST[i] = PQ.top().second;
        }
        else{
            DP[i] = V[i];
            ST[i] = i;
        }
    }

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

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

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