#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e17;
const int NMAX = 1e5 + 5;
int m, n;
ll A[NMAX], B[NMAX], C[NMAX], D[NMAX];
ll dpst[NMAX], dpdr[NMAX];
void normalizare() {
// normalizez 1, A, B, C, n
set <int> tot;
tot.insert(1); tot.insert(n);
for (int i = 1; i <= m; i++) {
tot.insert(A[i]);
tot.insert(B[i]);
tot.insert(C[i]);
}
map <int, int> nou;
int newN = 0;
for (auto x: tot)
nou[x] = ++newN;
for (int i = 1; i <= m; i++) {
A[i] = nou[A[i]];
B[i] = nou[B[i]];
C[i] = nou[C[i]];
}
n = newN;
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
}
normalizare();
if (A[1] == 1)
dpst[1] = D[1];
else
dpst[1] = INF;
if (B[1] == n)
dpdr[1] = D[1];
else
dpdr[1] = INF;
for (int i = 2; i <= m; i++) {
// dpst[i] = min{dpst[j] + d[i], cu C[j] intre A[i] si B[i]}
dpst[i] = INF;
if (A[i] == 1)
dpst[i] = D[i];
else for (int j = i - 1; j >= 1; j--)
if (A[i] <= C[j] && C[j] <= B[i])
dpst[i] = min(dpst[i], dpst[j] + D[i]);
dpdr[i] = INF;
if (B[i] == n)
dpdr[i] = D[i];
else for (int j = i - 1; j >= 1; j--)
if (A[i] <= C[j] && C[j] <= B[i])
dpdr[i] = min(dpdr[i], dpdr[j] + D[i]);
}
ll ans = INF;
for (int i = 1; i <= m; i++)
ans = min(ans, dpst[i] + dpdr[i] - D[i]);
ans < INF ? cout << ans : cout << -1;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
10 ms |
512 KB |
Output is correct |
| 18 |
Correct |
8 ms |
384 KB |
Output is correct |
| 19 |
Correct |
12 ms |
640 KB |
Output is correct |
| 20 |
Correct |
9 ms |
512 KB |
Output is correct |
| 21 |
Correct |
3 ms |
512 KB |
Output is correct |
| 22 |
Correct |
10 ms |
768 KB |
Output is correct |
| 23 |
Correct |
7 ms |
768 KB |
Output is correct |
| 24 |
Correct |
9 ms |
768 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
384 KB |
Output is correct |
| 17 |
Correct |
10 ms |
512 KB |
Output is correct |
| 18 |
Correct |
8 ms |
384 KB |
Output is correct |
| 19 |
Correct |
12 ms |
640 KB |
Output is correct |
| 20 |
Correct |
9 ms |
512 KB |
Output is correct |
| 21 |
Correct |
3 ms |
512 KB |
Output is correct |
| 22 |
Correct |
10 ms |
768 KB |
Output is correct |
| 23 |
Correct |
7 ms |
768 KB |
Output is correct |
| 24 |
Correct |
9 ms |
768 KB |
Output is correct |
| 25 |
Correct |
543 ms |
2680 KB |
Output is correct |
| 26 |
Execution timed out |
1086 ms |
7672 KB |
Time limit exceeded |
| 27 |
Halted |
0 ms |
0 KB |
- |
