Cod sursa(job #1876676)

Utilizator danyvsDan Castan danyvs Data 12 februarie 2017 15:37:28
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

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

const int NMAX = 50005;

int n, k;
long long V[NMAX];
long long S[NMAX];
int l, r;
long long sum_max;

void read()
{
    fin >> n >> k;
    for (int i = 1; i <= n; ++ i)
        fin >> V[i];
}

void precalc()
{
    for (int i = 1; i <= n; ++ i)
        S[i] = S[i - 1] + V[i];
}

void solve()
{
    sum_max = S[k];
    l = 1;
    r = k;
    for (int i = k + 1; i <= n; ++ i)
        {
         long long pmn = 1;
         for (int j = 2; j <= i - k + 1; ++ j)
            if (S[j] < S[pmn])
                pmn = j;
         if (S[i] - S[pmn] > sum_max)
            {
             sum_max = S[i] - S[pmn];
             l =  pmn + 1;
             r = i;
            }
        }
}

int main()
{
    read();
    fin.close();
    precalc();
    solve();
    fout << l << " " << r << " " << sum_max << "\n";
    fout.close();
    return 0;
}