Mai intai trebuie sa te autentifici.
Cod sursa(job #1494132)
| Utilizator | Data | 30 septembrie 2015 18:59:04 | |
|---|---|---|---|
| Problema | Deque | Scor | 60 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.72 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream in( "deque.in" );
ofstream out( "deque.out" );
struct shp
{
long long poz, val;
};
deque <shp> d;
void elimin( int val )
{
while( d.empty()==0 && d.back().val >= val )
{
d.pop_back();
}
}
int main( )
{
long long N, K, x, Ans= 0;
shp aux;
in >> N >> K;
for( int i= 1; i<=K; ++i )
{
in >> x;
elimin( x );
aux.poz= i;
aux.val= x;
d.push_back( aux );
}
Ans+= d.front().val;
for( int i= K+1; i<=N; ++i )
{
in >> x;
if( d.front().poz <= i-K ) d.pop_front();
elimin( x );
aux.val= x;
aux.poz= i;
d.push_back( aux );
Ans+= d.front().val;
}
out << Ans << '\n';
return 0;
}
