Cod sursa(job #2729461)

Utilizator emanuel2186Lugojan Emanuel emanuel2186 Data 24 martie 2021 19:10:37
Problema Deque Scor 25
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define Nmax 5000005
using namespace std;
ifstream fin("deque.in");
ofstream fout("deque.out");
int N, K;
int rez;
deque<int>v;
int loc;
int A[Nmax];
void actualizez(int poz)
{
    int last = A[v.back()];
    for(int i=v.size() - 2; i>=0; i--)
    {
        if(last <= A[ v[i] ])
        {
            v.erase(v.begin() + i);
        }
        else
            break;
    }
    if(v.front() == poz - K)
        v.pop_front();
}
void citire()
{
    fin>>N>>K;
    int x;
    for(int i=1; i<=N; i++)
    {
        fin>>A[i];
    }
    for(int i=1; i<=N; i++)
    {
        v.push_back(i);
        actualizez(i);
        if(i >= K)
            rez += A[v.front()];
    }
    fout<<rez<<"\n";
}
int main()
{
    citire();
    return 0;
}