Cod sursa(job #2221292)

Utilizator NashikAndrei Feodorov Nashik Data 13 iulie 2018 16:33:59
Problema Deque Scor 25
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
//#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
deque <int> dq;
const int MAX=10000005;
int main()
{
    ifstream cin("deque.in");
    ofstream cout("deque.out");
    int n,k,a,min1=MAX,min2=MAX,pos1,pos2,sum=0;
    cin>>n>>k;
    for(int 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;
            }
        }
    }
    //cout<<min1<<" "<<min2<<"\n";
    sum+=min1;
    for(int i=k+1;i<=n;i++){
        cin>>a;
        dq.pop_back();
        dq.push_back(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;
}