Submission #944954

#	Time	Username	Problem	Language	Result	Execution time	Memory
944954		siewjh	Meetings (IOI18_meetings)	C++17	19 / 100	687 ms	596984 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
const ll inf = 1e18;
ll lc[MAXN][MAXN], rc[MAXN][MAXN], ls[MAXN][MAXN], rs[MAXN][MAXN];

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
	int nums = H.size();
	vector<pair<int, ll>> vec;
	vec.push_back({-1, inf});
	for (int i = 0; i < nums; i++){
		while (vec.back().second <= H[i]) vec.pop_back();
		vec.push_back({i, H[i]});
		int curr = 1;
		for (int j = 0; j < i; j++){
			while (vec[curr].first < j) curr++;
			lc[i][j] = max(lc[i - 1][j], vec[curr].second);
		}
		lc[i][i] = ls[i][i] = H[i];
		for (int j = i - 1; j >= 0; j--) ls[i][j] = ls[i][j + 1] + lc[i][j];
	}
	vec.clear();
	vec.push_back({nums, inf});
	for (int i = nums - 1; i >= 0; i--){
		while (vec.back().second <= H[i]) vec.pop_back();
		vec.push_back({i, H[i]});
		int curr = 1;
		for (int j = nums - 1; j > i; j--){
			while (vec[curr].first > j) curr++;
			rc[i][j] = max(rc[i + 1][j], vec[curr].second);
		}
		rc[i][i] = rs[i][i] = H[i];
		for (int j = i + 1; j < nums; j++) rs[i][j] = rs[i][j - 1] + rc[i][j];
	}
	int queries = L.size();
	vector<ll> ans(queries);
	for (int q = 0; q < queries; q++){
		int l = L[q], r = R[q];
		ll res = inf;
		for (int m = l; m <= r; m++) res = min(res, ls[m][l] + rs[m][r] - H[m]);
		ans[q] = res;
	}
	return ans;
}

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