Cod sursa(job #2277510)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 6 noiembrie 2018 13:42:56
Problema Deque Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define MAXN 5000000

//int V[MAXN];
int* V;

struct ComparePair {
    bool operator() (const std::pair<int,int> & p1, const std::pair<int,int> & p2) const {
		if(p1.first == p2.first)
			return (p1.second < p2.second);
		else
			return (p1.first < p2.first);
    }
};

//set<pair<int,int>,ComparePair> multime;
vector<int> multime;

int N, K;
long long rez;

void findsum(){
	int min=multime[0];
	for(int j=1;j<K;j++){
		if(multime[j]<min)
			min=multime[j];
	}
	//rez+=(long long)(multime[0]);
	rez+=(long long)min;	
	vector<int>::iterator it;
	for(int i=K; i<N; i++){
		it=find(multime.begin(),multime.end(),V[i-K]);
		multime.erase(it);
		multime.push_back(V[i]);
	
		min=multime[0];
		for(int j=1;j<K;j++){
			if(multime[j]<min)
				min=multime[j];
		}		
		
		rez+=(long long)min;
		//rez+=(long long)(multime[0]);
	}
}

int main(){
	
	freopen("deque.in","rt",stdin);
	freopen("deque.out","wt",stdout);
	
	scanf("%d %d",&N,&K);
	V=new int[N];
	multime.reserve(K);

	for(int i=0;i<N;i++){
		scanf("%d",&V[i]);
		if(i<K)
			multime.push_back(V[i]);
	}
	
	findsum();

	printf("%lld",rez);

	return 0;
}