#include <bits/stdc++.h>
#define in cin
#define out cout
#define int long long
using namespace std;
//ifstream in("in.in");
//ofstream out("out.out");
struct device {
int l, r, hole, cost;
};
vector<device> devices;
const int nmax = 20, mmax = 1005, inf = (1LL << 60);
int n, m, dp[nmax][mmax][mmax];
void minSelf(int &a, int b) {
if (b < a) {
a = b;
}
}
int32_t main() {
in >> n >> m;
if (m == 1) {
out << "0\n";
return 0;
}
devices.resize(n + 1);
for (int i = 1; i <= n; i++) {
int l, r, hole, cost;
in >> l >> r >> hole >> cost;
devices[i] = {l, r, hole, cost};
}
/// dp[i][l][r] = using only devices i...n, we have extended the road for the interval
/// l - r. sum will be in dp[1][1..m]
for (int i = 0; i <= n + 1; i++) {
for (int l = 0; l <= m; l++) {
for (int r = 0; r <= m; r++) {
dp[i][l][r] = inf;
}
}
}
for (int i = m; i >= 1; i--) {
dp[n + 1][i][i] = 0;
}
for (int i = n; i >= 1; i--) {
for (int l = 1; l <= m; l++) {
for (int r = l; r <= m; r++) {
if (dp[i + 1][l][r] == inf) continue;
if (l <= devices[i].hole && devices[i].hole <= r) {
int newL = min(l, devices[i].l);
int newR = max(r, devices[i].r);
minSelf(dp[i][newL][newR], dp[i + 1][l][r] + devices[i].cost);
minSelf(dp[i][l][r], dp[i + 1][l][r]);
minSelf(dp[i][newL][newR], dp[i + 1][newL][newR]);
}
}
}
}
if (dp[1][1][m] == inf) {
out << "-1\n";
} else {
out << dp[1][1][m] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
