This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby
typedef long long ll;
struct Device {
int a, b, c, d;
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
int n, m;
std::cin >> n >> m;
Device a[n + 1];
std::vector<int> norm;
norm.push_back(1);
norm.push_back(m);
for (int i = 1; i <= n; i++) {
std::cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d;
norm.push_back(a[i].c);
}
std::sort(norm.begin(), norm.end());
norm.erase(std::unique(norm.begin(), norm.end()), norm.end());
for (int i = 1; i <= n; i++) {
a[i].a = std::lower_bound(norm.begin(), norm.end(), a[i].a) - norm.begin() + 1;
a[i].b = std::lower_bound(norm.begin(), norm.end(), a[i].b) - norm.begin() + 1;
a[i].c = std::lower_bound(norm.begin(), norm.end(), a[i].c) - norm.begin() + 1;
}
int sz = (int) norm.size();
ll dpl[n + 1][sz + 1];
ll dpr[n + 1][sz + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= sz; j++) {
dpl[i][j] = dpr[i][j] = 1e18;
}
}
dpl[0][1] = 0;
dpr[0][sz] = 0;
ll answer = 1e18;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sz; j++) {
dpl[i][j] = std::min(dpl[i][j], dpl[i - 1][j]);
dpr[i][j] = std::min(dpr[i][j], dpr[i - 1][j]);
int k = j;
if (a[i].a <= k && k <= a[i].b) {
k = a[i].c;
}
dpl[i][k] = std::min(dpl[i][k], dpl[i - 1][j] + a[i].d);
dpr[i][k] = std::min(dpr[i][k], dpr[i - 1][j] + a[i].d);
}
for (int j = 1; j <= sz; j++) {
answer = std::min(answer, dpl[i][j] + dpr[i][j]);
for (int p = a[i].a; p <= a[i].b; p++) {
answer = std::min(answer, dpl[i][a[i].c] + dpr[i - 1][p]);
}
}
}
if (answer == 1e18) {
answer = -1;
}
std::cout << answer;
return 0;
}
Compilation message (stderr)
pinball.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
6 | #warning That's the baby, that's not my baby
| ^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |