Pagini recente » Cod sursa (job #313501) | Cod sursa (job #298684) | Cod sursa (job #1193870) | Borderou de evaluare (job #336502) | Cod sursa (job #2166895)
#define x first
#define y second
#include <deque>
#include <cstdio>
using namespace std;
deque < pair < long long , long long > > D;
const int Dim = 5000001;
long long n,k;
long long sum;
void Get (long long &x);
int main() {
freopen("deque.in", "r" , stdin);
freopen ("deque.out" , "w" , stdout);
long long q;
Get(n);Get(k);Get(q);
D.push_front({q, 1});
int i;
for(i = 2; i <= k; ++i)
{
Get(q);
while(D.back().x >= q and D.size())
D.pop_back();
D.push_back({q,i});
}
sum = D.front().x;
for(; i <= n; ++i)
{
Get(q);
while(D.back().x >= q and D.size())
D.pop_back();
D.push_back({q,i});
while(i - D.front().y == k and D.size())
D.pop_front();
sum += D.front().x;
}
printf("%d",sum);
}
const int Lim = 1000000;
int u = Lim - 1;
char s[Lim];
void Next() {
if ( ++u == Lim)
fread(s,1,Lim,stdin) , u = 0;
}
void Get (long long &x) {
bool semn = false;
for (; s[u] < '0' || s[u] > '9'; Next());
for (x = 0; s[u] >= '0' && s[u] <= '9'; Next())
{ if ( s[u-1] == '-')
semn = true;
x = x * 10 + s[u] - '0';
}
if( semn == true)
x*=-1;
}