Submission #133230

#	Time	Username	Problem	Language	Result	Execution time	Memory
133230		groeneprof	Meetings (IOI18_meetings)	C++14	0 / 100	5586 ms	504724 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct sliding_minimum{
	long long l, val;
	deque<pair<long long,int> > deq;
	sliding_minimum(int _l, vector<int> v){
		l = _l;
		val = 0;
		for(int i = 0; i<l; i++){
			add(v[i]);
		}
	}
	void add(int a){
		int i = 1;
		while(!deq.empty()&&deq.back().first<=a){
			i+=deq.back().second;
			val-= deq.back().first * deq.back().second;
			deq.pop_back();
		}
		val+=a*i;
		deq.push_back({a, i});
	}

	void remove(){
		val -= deq.front().first;
		if(deq.front().second==1){
			deq.pop_front();
		}
		else{
			deq.front().second--;
		}
	}
	void slide(int a){
		add(a);
		remove();
	}
};
int N, Q;

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	N = H.size();
	Q = L.size();
	vector<vector<int> > prec1(N, vector<int> (N, -1));
	for(int i = 1; i<=N; i++){
		sliding_minimum sm(i, H);
		for(int j = 0; i+j-1<N;j++){
			prec1[j][j+i-1] = sm.val;
			//cout<<"i: "<<j<<" j: "<<j+i-1<<"  :   "<<sm.val<<endl;
			if(i+j<N) sm.slide(H[j+i]);
		}
	}
	reverse(H.begin(), H.end());
	vector<vector<int> > prec2(N, vector<int> (N, -1));
	for(int i = 1; i<=N; i++){
		sliding_minimum sm(i, H);
		for(int j = 0; i+j-1<N;j++){
			prec2[N-1-(j+i-1)][N-1-j] = sm.val;
			if(i+j<N) sm.slide(H[j+i]);
		}
	}
	reverse(H.begin(), H.end());
	vector<long long> C(Q);
	for(int i = 0; i<Q; i++){
		long long ans = 2e18;
		for(int j = L[i]; j<=R[i]; j++){
			ans = min(ans, prec1[L[i]][j] + prec2[j][R[i]] - (long long)H[j]);
		}
		C[i] = ans;
	}
	return C;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40