Submission #133239

#	Time	Username	Problem	Language	Result	Execution time	Memory
133239		groeneprof	모임들 (IOI18_meetings)	C++14	19 / 100	2202 ms	786436 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct sliding_minimum{
	int l, val;
	deque<pair<int,int> > deq;
	sliding_minimum(int _l, vector<signed> 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<int> minimum_costs(vector<signed> H, vector<signed> L, vector<signed> 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<int> C(Q);
	for(int i = 0; i<Q; i++){
		int ans = 2e18;
		for(int j = L[i]; j<=R[i]; j++){
			ans = min(ans, prec1[L[i]][j] + prec2[j][R[i]] - (int)H[j]);
		}
		C[i] = ans;
	}
	return C;
}

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