Submission #955814

#	Time	Username	Problem	Language	Result	Execution time	Memory
955814		vjudge1	Sparklers (JOI17_sparklers)	C++17	0 / 100	3 ms	18780 KiB

sparklers

#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: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50