Cod sursa(job #3145415)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 15 august 2023 14:24:23
Problema Deque Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("deque.in");
ofstream cout("deque.out");
int v [ 200005 ];
int main()
{long long n , k ;
    deque<int> dq ;
    cin >> n >> k ;
   for ( int i = 1; i <= k ; i ++ )
   {
       cin >> v[ i ] ;

       while ( !dq.empty() && v[dq.back()] > v [ i ] )
        dq.pop_back();

       dq.push_front( i ) ;

   }



   long long sum = 0 ;
   sum += v[dq.back()];

   for ( int i = k + 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 );

       sum += v[dq.back()];


   }
   cout << sum ;
    return 0;
}