Submission #427549

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

meetings

#include "meetings.h"
#include <algorithm>
using namespace std;

#define sz(x) (int)x.size()

const long long INF = 1e18;

void calc(int x, vector<int>& H, vector<vector<long long>>& pref, vector<vector<long long>>& suff) {
	long long hi;

	pref[x][x] = H[x];
	hi = H[x];

	for(int i=x-1; i>=0; i--) {
		hi = max(hi, (long long)H[i]);
		pref[x][i] = pref[x][i+1] + hi;
	}

	if(x+1 < sz(H)) {
		suff[x][x+1] = H[x+1];
		hi = H[x+1];

		for(int i=x+2; i<sz(H); i++) {
			hi = max(hi, (long long)H[i]);
			suff[x][i] = suff[x][i-1] + hi;
		}
	}
}

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
	int Q = sz(L);

	vector<vector<long long>> pref(sz(H), vector<long long>(sz(H)));
	vector<vector<long long>> suff(sz(H), vector<long long>(sz(H)));

	for(int x=0; x<sz(H); x++) calc(x, H, pref, suff);

	vector<long long> ret(Q, INF);

	for(int i=0; i<Q; i++) {
		for(int x=L[i]; x<=R[i]; x++) {
			if(x != R[i])
				ret[i] = min(ret[i], pref[x][L[i]] + suff[x][R[i]]);

			else
				ret[i] = min(ret[i], pref[x][L[i]]);
		}	
	}

	return ret;
}

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