oj.uz

Submission #955815

# Submission time Handle Problem Language Result Execution time Memory
955815 2024-03-31T12:48:39 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 292 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;
	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]);
    }
	if (compress.empty() || *compress.begin() > 1 || *compress.rbegin() < n) {
		cout << (n == 1 ? 0 : -1);
		return 0;
	}
	map <int, int> cmap;
	n = 0;
	for (auto &x : compress) cmap[x] = 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 8536 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 2 ms 19016 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 2 ms 19016 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 78 ms 181892 KB Output is correct
10 Correct 82 ms 273336 KB Output is correct
11 Correct 92 ms 323924 KB Output is correct
12 Runtime error 292 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 8536 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 2 ms 19016 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 78 ms 181892 KB Output is correct
10 Correct 82 ms 273336 KB Output is correct
11 Correct 92 ms 323924 KB Output is correct
12 Runtime error 292 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 8536 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 19036 KB Output is correct
5 Correct 2 ms 19016 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 78 ms 181892 KB Output is correct
10 Correct 82 ms 273336 KB Output is correct
11 Correct 92 ms 323924 KB Output is correct
12 Runtime error 292 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -