Cod sursa(job #1103916)
| Utilizator | Data | 10 februarie 2014 09:17:24 | |
|---|---|---|---|
| Problema | Deque | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.54 kb |
# include <cstdio>
# include <deque>
using namespace std;
int i,j,n,k;
long long VV;
int v[5000005];
deque <int> d;
int main ()
{
freopen ("deque.in", "r", stdin);
freopen ("deque.out", "w", stdout);
scanf ("%d%d", &n, &k);
for (i=1; i<=n; ++i)
{
scanf ("%d", &v[i]);
while (!d.empty () && v[i]<v[d.back()])
d.pop_back();
d.push_back(i);
if (d.front()==i-k) d.pop_front ();
if (i>=k) VV+=v[d.front()];
}
printf ("%lld\n", VV);
return 0;
}
