Submission #955767

#	Time	Username	Problem	Language	Result	Execution time	Memory
955767		vjudge1	Pinball (JOI14_pinball)	C++17	11 / 100	151 ms	524288 KiB

pinball

#include <iostream>
#include <set>
#include <map>
#include <climits>
#define int long long
using namespace std;

const int M = 205, K = 605, INF = 1e15;
int intl[M], intr[M], to[M], cost[M], dp[M][K][K], m, n, k;

int calc(int i, int l, int r) {
	if (l == 0 && r == k - 1) return 0LL;
	if (i == -1) return INF;
	int &dpr = dp[i][l][r];
	if (dpr == -1) {
		dpr = calc(i - 1, l, r);
		if (l <= to[i] && to[i] <= r && !(l <= intl[i] && intr[i] <= r)) {
			// cerr << "the interval [" << l << "-" << r << "] catches " << i << ": " << intl[i] << '-' << intr[i] << " to " << to[i] << endl;
			dpr = min(dpr, cost[i] + calc(i - 1, min(intl[i], l), max(intr[i], r)));
		}
		// fprintf(stderr, "dp[%lld][%lld][%lld] = %lld\n", i, l, r, dpr);
	}
	return dpr;
}

signed main() {
	#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#endif

	cin >> m >> n;
	set <int> compress;
	for (int i = 0; i < m; i++) {
		cin >> intl[i] >> intr[i] >> to[i] >> cost[i];
		compress.insert(intl[i]);
		compress.insert(intr[i]);
		compress.insert(to[i]);
	}
	if (*compress.begin() > 1 || *compress.rbegin() < n) {
		cout << -1;
		return 0;
	}
	map <int, int> compressidx;
	for (auto &x : compress) {
		compressidx[x] = k++;
	}
	for (int _1 = 0; _1 <= m; _1++) {
		for (int _2 = 0; _2 <= k; _2++) {
			for (int _3 = 0; _3 <= k; _3++) {
				dp[_1][_2][_3] = -1;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		intl[i] = compressidx[intl[i]];
		intr[i] = compressidx[intr[i]];
		to[i] = compressidx[to[i]];
	}
	int mn = LLONG_MAX;
	for (int i = 0; i < k; i++) {
		if (mn > calc(m - 1, i, i)) mn = calc(m - 1, i, i);
	}
	if (mn >= INF) mn = -1;
	cout << mn;
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49