Submission #392680

#	Time	Username	Problem	Language	Result	Execution time	Memory
392680		JimmyZJX	Meetings (IOI18_meetings)	C++14	19 / 100	406 ms	420244 KiB

meetings

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

int maxH[5003][5003];

LL dp[5003][5003];
int maxI[5003];

VL minimum_costs(Vi H, Vi L, Vi R) {
	int n = H.size(), q = L.size();

	memset(dp, 0, sizeof(dp));

	forR(i, n) {
		dp[i][i] = H[i];
		maxI[i] = i;
	}
	for (int d = 1; d < n; d++) {
		for (int i = 0; i + d < n; i++) {
			int j = i + d;
			if (H[j] > H[maxI[i]]) maxI[i] = j;

			int mi = maxI[i];
			if (mi == i) {
				dp[i][j] = H[i] + dp[i + 1][j];
			} else if (mi == j) {
				dp[i][j] = H[j] + dp[i][j - 1];
			} else {
				LL hMax = H[mi];
				dp[i][j] = min(dp[i][mi - 1] + hMax * (j - mi + 1),
					dp[mi + 1][j] + hMax * (mi - i + 1));
			}
		}
	}

#ifdef TEST_LOCAL
	// check
	forR(i, n) for (int j = i; j < n; j++) {
		maxH[i][j] = H[i];
		for (int x = i + 1; x <= j; x++) {
			maxH[i][j] = max(maxH[i][j], H[x]);
		}
	}
	forR(i, n) for (int j = i; j < n; j++) {
		bool hasEq = false;
		for (int x = i; x <= j; x++) {
			LL cost = 0;
			for (int a = i; a <= x; a++) cost += maxH[a][x];
			for (int a = x + 1; a <= j; a++) cost += maxH[x][a];
			assert(dp[i][j] <= cost);
			if (dp[i][j] == cost) hasEq = true;
		}
		assert(hasEq);
	}
#endif

	VL ans;
	forR(i, q) {
		ans.push_back(dp[L[i]][R[i]]);
	}

	return ans;
}

#ifdef TEST_LOCAL
int main() {
	minimum_costs(Vi{ 1000000000, 1000000000, 1, 1000000000, 1000000000 }, Vi{ 0, 1 }, Vi{ 1,2 });

	return 0;
}
#endif

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