Mai intai trebuie sa te autentifici.
Cod sursa(job #1861768)
| Utilizator | Data | 29 ianuarie 2017 11:52:58 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.9 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream f("deque.in");
ofstream g("deque.out");
int n,k;
int i;
struct a{
int poz;
int val;
}x;
struct b{
long long poz;
long long val;
};
deque <a>q;
int main()
{
f >> n >> k;
for(i = 1 ; i <= k ; ++i){
f >> x.val;
x.poz = i;
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
}
b smin;
smin.val = q.front().val;
smin.poz = q.front().poz;
int capats = 1;
int capatd = k;
for(i = k + 1 ; i <= n ; ++i){
f >> x.val;x.poz = i;
capats++;
capatd++;
if(q.front().poz < capats)q.pop_front();
while(!q.empty() && q.back().val > x.val)
q.pop_back();
q.push_back(x);
smin.val += q.front().val;
}
g << smin.val;
return 0;
}
