Cod sursa(job #2540789)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 7 februarie 2020 18:46:14
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>
#define MAXX 5000005

using namespace std;

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

int n, k, st, dr;
int v[MAXX], d[MAXX];
int sol;

int main(){
     fin>>n>>k;
     for(int i=1; i<=n; i++)
          fin>>v[i];

     st=dr=1;
     d[1]=1;
     for(int i=2; i<=n; i++){
          while(st <= dr && v[i] < v[d[dr]])
               dr--;
          d[++dr]=i;

          if(i - d[st] == k)
               st++;
          if(i >= k)
               sol+=v[d[st]];
     }

     fout<<sol;
     return 0;
}