Cod sursa(job #2221314)

Utilizator NashikAndrei Feodorov Nashik Data 13 iulie 2018 18:07:47
Problema Deque Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
//#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
deque <long long> dq;
const long long MAX=10000005;
int main()
{
    ifstream cin("deque.in");
    ofstream cout("deque.out");
    long long n,k,a,min1=MAX,min2=MAX,pos1,pos2,sum=0;
    cin>>n>>k;
    for(long long i=1;i<=k;i++){
        cin>>a;
        dq.push_front(a);
        if(min1>a){
            min1=a;
            pos1=i;
            min2=MAX;
        }
        else{
            if(min1<=a and min2>=a){
                min2=a;
                pos2=i;
            }
        }
    }
    //cout9<<min1<<" "<<min2<<"\n";
    sum+=min1;
    for(long long i=k+1;i<=n;i++){
        cin>>a;
        dq.pop_back();
        dq.push_front(a);
        if(min1>a){
            min1=a;
            pos1=i;
            min2=MAX;
        }
        else{
            if(min1<=a and min2>=a){
                min2=a;
                pos2=i;
            }
        }
        if(i==pos1+k){
            min1=min2;
            pos1=pos2;
            min2=MAX;
        }
        sum+=min1;
        //cout<<min1<<" "<<min2<<"\n";
    }
    cout<<sum;
    return 0;
}