Cod sursa(job #598849)

Utilizator deneoAdrian Craciun deneo Data 27 iunie 2011 13:30:05
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <deque>
using namespace std;

int n, k, v[50010], sum[50010], maxsum, pstart, pfinal;

deque<int> dq;

void insert(int poz)
{
    while(!dq.empty() && sum[dq[dq.size() - 1]] > sum[poz]) dq.pop_back();
    dq.push_back(poz);
}

int getMin()
{
    return dq.front();
}

int main()
{
    int i, a;

    ifstream f("secv2.in");
    ofstream g("secv2.out");
    f >> n >> k;
    for(i = 1; i <= n; ++i)
        f >> v[i];

    for(i = 1; i <= n; ++i)
        sum[i] = v[i] + sum[i - 1];

    for(i = k; i <= n; ++i)
    {
        insert(i - k);
        a = getMin();
        if(sum[i] - sum[a] > maxsum)
        {
            maxsum = sum[i] - sum[a];
            pstart = a + 1;
            pfinal = i;
        }
    }

    g << pstart << ' ' << pfinal << ' ' << maxsum << '\n';
    g.close();
    return 0;
}