Cod sursa(job #1831828)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 18 decembrie 2016 20:29:10
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int nMax = 50005;
const int INF = (1 << 29);

int n, k;
int v[nMax];
int dp[nMax];

void citire()
{
    in >> n >> k;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
}

void rezolvare()
{
    int st, dr, rasp = -INF, mnpos;
    int mn = INF;

    for(int i = 1; i < k; ++i)
        dp[i] = dp[i-1] + v[i];

    for(int i = k; i <= n; ++i)
    {
        dp[i] = dp[i-1] + v[i];
        if(dp[i - k] < mn)
        {
            mn = dp[i - k];
            mnpos = i - k + 1;
        }
        if(dp[i] - mn > rasp)
        {
            rasp = dp[i] - mn;
            st = mnpos;
            dr = i;
        }
    }

    out << st << " " << dr << " " << rasp;
}

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