Cod sursa(job #2624633)
Utilizator | Data | 5 iunie 2020 01:36:57 | |
---|---|---|---|
Problema | Deque | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <fstream>
using namespace std;
ifstream fin( "deque.in" );
ofstream fout( "deque.out" );
struct nod
{ long long val;
int poz;
};
nod st[5000005];
long long n, k, x, top, pr, sum;
int main()
{
int i;
fin >> n >> k;
fin >> x;
pr = 1;
top = 1;
st[1].val = x;
st[1].poz = 1;
for( i = 2; i <= n; i++ ) {
fin >> x;
if(i - st[pr].poz + 1 > k) pr++;
while(x < st[top].val && top >= pr) top--;
top++;
st[top].val = x;
st[top].poz = i;
if(i < k) sum += st[pr].val;
}
fout << sum;
return 0;
}