Cod sursa(job #2603827)

Utilizator avtobusAvtobus avtobus Data 20 aprilie 2020 23:04:01
Problema Deque Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;

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

int main(void) {
  // freopen("deque.in", "r", stdin);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n, k, a;
  fin >> n >> k;
  deque<pii> dq;
  ll ans = 0;

  rep(i, n) {
    while(!dq.empty() && dq.front().second + k-1 < i) {
      dq.pop_front();
    }
    fin >> a;
    while(!dq.empty() && dq.back().first >= a) {
      dq.pop_back();
    }
    dq.push_back({a, i});
    if (i >= k-1) {
      ans += dq.front().first;
    }
  }
  fout << ans << endl;

  return 0;
}