Cod sursa(job #2277509)

Utilizator cezar.plescaCezar Plesca cezar.plesca Data 6 noiembrie 2018 13:35:14
Problema Deque Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 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(){
	sort(multime.begin(), multime.end());
	rez+=(long long)(multime[0]);
	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]);
		sort(multime.begin(), multime.end());	
		rez+=(long long)(multime[0]);
	}
}

int main(){
	
	freopen("deque.in","rt",stdin);
	freopen("deque.out","wt",stdout);
	
	scanf("%d %d",&N,&K);
	//V.reserve(N);
	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;
}