Cod sursa(job #3145422)
Utilizator | Data | 15 august 2023 14:41:07 | |
---|---|---|---|
Problema | Deque | Scor | 45 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
long long v [ 5000005 ];
int main()
{
long long n, k ;
deque<long long> dq ;
cin >> n >> k ;
long long sum = 0;
for ( int i = 1 ; i <= n ; i ++ )
{
cin >> v[ i ];
while (!dq.empty() && i - k + 1 > dq.back() )
{
dq.pop_back();
}
while ( !dq.empty() && v[dq.back()] >= v [ i ] )
dq.pop_back();
dq.push_front( i );
if ( i >= k )
sum += v[dq.back()];
}
cout << sum ;
return 0;
}