oj.uz

Submission #956009

# Submission time Handle Problem Language Result Execution time Memory
956009 2024-03-31T19:28:19 Z EntityPlantt Pinball (JOI14_pinball) C++14
11 / 100
 213 ms 524292 KB 
#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 0;
	if (l < 0 || r >= k || i < 0) 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.empty() || *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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20824 KB Output is correct
5 Correct 3 ms 21332 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20824 KB Output is correct
5 Correct 3 ms 21332 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 89 ms 167508 KB Output is correct
10 Correct 115 ms 264368 KB Output is correct
11 Correct 126 ms 315968 KB Output is correct
12 Runtime error 213 ms 524292 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20824 KB Output is correct
5 Correct 3 ms 21332 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 89 ms 167508 KB Output is correct
10 Correct 115 ms 264368 KB Output is correct
11 Correct 126 ms 315968 KB Output is correct
12 Runtime error 213 ms 524292 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20824 KB Output is correct
5 Correct 3 ms 21332 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 3 ms 20828 KB Output is correct
9 Correct 89 ms 167508 KB Output is correct
10 Correct 115 ms 264368 KB Output is correct
11 Correct 126 ms 315968 KB Output is correct
12 Runtime error 213 ms 524292 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -