#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
18780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
