| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 314246 |
2020-10-19T08:41:39 Z |
lauran |
Pinball (JOI14_pinball) |
C++14 |
|
1000 ms |
632 KB |
#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];
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++) {
cin >> A[i] >> B[i] >> C[i] >> D[i];
}
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 <= n; 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 <= n; i++)
ans = min(ans, dpst[i] + dpdr[i] - D[i]);
ans < INF ? cout << ans : cout << -1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Execution timed out |
1097 ms |
632 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Execution timed out |
1097 ms |
632 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
4 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
4 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Execution timed out |
1097 ms |
632 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
