Cod sursa(job #1192774)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 29 mai 2014 19:14:08
Problema Deque Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>

#define st first
#define nd second

using namespace std;

typedef long long int64;

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

int N, K;
deque<pair<int64, int> > D;

int main()
{
    int i;
    int64 value, result = 0;

    fin >> N >> K;
    --K;

    for (i = 0; i < N; ++i)
    {
        fin >> value;

        while(!D.empty() && value <= D.back().st)
            D.pop_back();

        D.push_back(make_pair(value, i));

        if (D.back().nd - D.front().nd > K)
            D.pop_front();

        if (i < K) continue;
        result += D.front().st;
    }

    fout << result << '\n';

	fin.close();
	fout.close();
	return 0;
}