Cod sursa(job #2166895)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 13 martie 2018 19:22:36
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#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;
}