oj.uz

답안 #955717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
955717 2024-03-31T11:07:56 Z vjudge1 Pinball (JOI14_pinball) C++17
0 / 100
 3 ms 21084 KB 
#include <iostream>
#include <set>
#include <map>
#include <climits>
#define int long long
using namespace std;

const signed M = 205, K = 605;
const int 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 (i == -1) return (l == 0 && r == k - 1) ? 0LL : 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 << "te 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]);
	}
	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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 2 ms 21084 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 2 ms 21084 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 2 ms 21084 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 16732 KB Output is correct
3 Correct 3 ms 20828 KB Output is correct
4 Correct 3 ms 20828 KB Output is correct
5 Correct 3 ms 21084 KB Output is correct
6 Correct 3 ms 20828 KB Output is correct
7 Incorrect 2 ms 21084 KB Output isn't correct
8 Halted 0 ms 0 KB -