Cod sursa(job #2729842)
Utilizator | Data | 25 martie 2021 14:54:36 | |
---|---|---|---|
Problema | Deque | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <fstream>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
int dq[5000010];
int main()
{
int n, k;
cin>>n>>k;
int v[n+1];
for(int i = 1; i <= n; i++)
cin>>v[i];
int left = 1, right = 0;
long long sol = 0;
for (int i = 1; i <= n; i++)
{
while(left <= right && v[i] <= v[dq[right]])
right -= 1;
right += 1;
dq[right] = i;
if (dq[left] == i - k)
left += 1;
if (i >= k)
sol += v[dq[left]];
}
cout<<sol;
return 0;
}