#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 5005, INF = 3.9e18;
int m, n;
int ans = INF;
struct P {
int t, l, r, c;
int time, bound, pos, exp;
P() {}
P(int _t, int _l, int _r, int _c) : t(_t), l(_l), r(_r), c(_c) {
time = r + t;
bound = r - t;
pos = l - t;
exp = l + t;
}
} p[MXN];
ostream &operator<<(ostream &ss, P p) {
ss << '<' << p.t << ' ' << p.l << ' ' << p.r << ' ' << p.c << '>';
return ss;
}
vector<P> head, tail;
struct Q {
int t, b, c;
Q() {}
Q(int _t, int _b, int _c) : t(_t), b(_b), c(_c) {}
};
vector<Q> sen;
int CIN(int n) {
int t, l, r, c;
int C = 0;
FOR(i, 0, n) {
cin >> t >> l >> r >> c;
if (l == 1 && r == m) {
ans = min(ans, c);
continue;
}
// if (l == 1) head.push_back(P(t, l - 1, r, c));
if (r == m) tail.push_back(P(t, l - 1, r, c));
else {
p[C] = P(t, l - 1, r, c);
if (l == 1) p[C].exp = -INF;
C++;
}
}
return C;
}
void miku() {
cin >> m >> n;
if (n >= MXN) return;
n = CIN(n);
sort(p, p + n, [](P a, P b) -> bool {
return a.time < b.time;
});
// for (auto &p : head) sen.push_back(Q(p.time, p.bound, p.c));
sen.push_back(Q(0, 0, 0));
FOR(i, 0, n) {
// debug(i, p[i]);
// debug(p[i].exp);
int sml = INF;
for (auto &j : sen) {
if (j.t < p[i].exp) continue;
if (j.t == p[i].time) continue;
if (j.b < p[i].pos) continue;
sml = min(sml, j.c);
}
// debug(sml);
sen.push_back(Q(p[i].time, p[i].bound, sml + p[i].c));
}
for (auto &p : tail) {
for (auto &j : sen) {
if (j.t < p.exp) continue;
if (j.b < p.pos) continue;
ans = min(ans, p.c + j.c);
}
}
cout << (ans == INF ? -1 : ans) << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
