oj.uz

Submission #955816

# Submission time Handle Problem Language Result Execution time Memory
955816 2024-03-31T12:49:53 Z vjudge1 Pinball (JOI14_pinball) C++17
11 / 100
 177 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;
		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 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 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 8540 KB Output is correct
2 Correct 2 ms 14684 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 34 ms 185536 KB Output is correct
10 Correct 67 ms 277780 KB Output is correct
11 Correct 87 ms 327256 KB Output is correct
12 Runtime error 177 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 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 34 ms 185536 KB Output is correct
10 Correct 67 ms 277780 KB Output is correct
11 Correct 87 ms 327256 KB Output is correct
12 Runtime error 177 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 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 19036 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 34 ms 185536 KB Output is correct
10 Correct 67 ms 277780 KB Output is correct
11 Correct 87 ms 327256 KB Output is correct
12 Runtime error 177 ms 524288 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -