Submission #97338

#	Time	Username	Problem	Language	Result	Execution time	Memory
97338		E869120	Meetings (IOI18_meetings)	C++14	19 / 100	1143 ms	117800 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

long long N, Q, H[5009], T[5009]; pair<int, int> dp[5009][5009];

void dfs(int cl, int cr) {
	if (cl > cr) return;
	int cm = dp[cl][cr].second; long long cost = dp[cl][cr].first;
	//cout << "cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", cost = " << cost << endl;
	T[cl] += cost * (cr - cm + 1);
	T[cm] += cost * (cm - cl);
	T[cm + 1] -= cost * (cr - cm);
	T[cr + 1] -= cost * (cm - cl + 1);
	dfs(cl, cm - 1);
	dfs(cm + 1, cr);
}

vector<long long> minimum_costs(vector<int> HH, vector<int> L, vector<int> R) {
	N = HH.size(); Q = L.size();
	for (int i = 0; i < N; i++) H[i] = HH[i];
	
	for (int i = 0; i < N; i++) {
		pair<int, int> BASE = make_pair(-1, -1);
		for (int j = i; j < N; j++) {
			BASE = max(BASE, make_pair((int)H[j], j));
			dp[i][j] = BASE;
		}
	}
	
	vector<long long> ans;
	for (int i = 0; i < Q; i++) {
		for (int j = 0; j <= N; j++) T[j] = 0;
		dfs(L[i], R[i]);
		for (int j = 1; j <= N; j++) T[j] += T[j - 1];
		
		long long rem = (1LL << 60);
		for (int j = L[i]; j <= R[i]; j++) rem = min(rem, T[j]);
		ans.push_back(rem);
	}
	return ans;
}

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