oj.uz

Submission #955819

# Submission time Handle Problem Language Result Execution time Memory
955819 2024-03-31T12:57:38 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 219 ms 524288 KB 
#include <iostream>
#include <array>
#include <set>
#include <map>
using namespace std;
#define int long long

const int M = 205, N = 605, INF = 1e15;
int m, n, dp[M][N][N];
array <int, 4> dev[M];

int calc(int i, int l, int r) {
	if (l <= 0 && r >= n - 1) return 0;
	if (l > r || l < 0 || r >= n || i < 0) return INF;
	int &dpr = dp[i][l][r];
	if (dpr != -1) return dpr;
	dpr = calc(i - 1, l, r);
	if (l <= dev[i][2] && dev[i][2] <= r) dpr = min(dpr, dev[i][3] + calc(i - 1, min(dev[i][0], l), max(dev[i][1], r)));
	// cerr << "dp[" << i << "][" << l << "][" << r << "] = " << dpr << endl;
	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;
	compress.insert(1);
	compress.insert(n);
	for (int i = 0; i < m; i++) {
		cin >> dev[i][0] >> dev[i][1] >> dev[i][2] >> dev[i][3];
		compress.insert(dev[i][0]);
		compress.insert(dev[i][1]);
		compress.insert(dev[i][2]);
	}
	map <int, int> cmap;
	n = 0;
	for (auto &x : compress) {
		cmap[x] = n;
		n++;
	}
	for (int i = 0; i < m; i++) {
		dev[i][0] = cmap[dev[i][0]];
		dev[i][1] = cmap[dev[i][1]];
		dev[i][2] = cmap[dev[i][2]];
	}
	for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) dp[i][j][k] = -1;
	int mn = INF;
	for (int i = 0; i < n; i++) mn = min(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 1 ms 8540 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 5 ms 19008 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 3 ms 18776 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 5 ms 19008 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 3 ms 18776 KB Output is correct
9 Correct 74 ms 187220 KB Output is correct
10 Correct 79 ms 279888 KB Output is correct
11 Correct 89 ms 328532 KB Output is correct
12 Runtime error 219 ms 524288 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 1 ms 8540 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 5 ms 19008 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 3 ms 18776 KB Output is correct
9 Correct 74 ms 187220 KB Output is correct
10 Correct 79 ms 279888 KB Output is correct
11 Correct 89 ms 328532 KB Output is correct
12 Runtime error 219 ms 524288 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 1 ms 8540 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 5 ms 19008 KB Output is correct
4 Correct 2 ms 19036 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 19036 KB Output is correct
8 Correct 3 ms 18776 KB Output is correct
9 Correct 74 ms 187220 KB Output is correct
10 Correct 79 ms 279888 KB Output is correct
11 Correct 89 ms 328532 KB Output is correct
12 Runtime error 219 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -