# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
219379 | 2020-04-05T08:14:02 Z | ho94949 | Treatment Project (JOI20_treatment) | C++17 | 3000 ms | 3576 KB |
#include <bits/stdc++.h> using namespace std; const int MAXM = 1e5; const long long INF = 0x3f3f3f3f3f3f3f3fLL; int N, M; int T[MAXM], L[MAXM], R[MAXM], C[MAXM]; int XL[MAXM], YL[MAXM], XR[MAXM], YR[MAXM]; bool vis[MAXM]; int main() { scanf("%d%d", &N, &M); for(int i=0; i<M; ++i) { scanf("%d%d%d%d", T+i, L+i, R+i, C+i); --L[i]; //L[i] = 0, R[i] = N covers whole XL[i] = L[i]-T[i], YL[i] = L[i]+T[i]; XR[i] = R[i]-T[i], YR[i] = R[i]+T[i]; } using pli = pair<long long, int>; priority_queue<pli, vector<pli>, greater<pli>> Q; for(int i=0; i<M; ++i) if(L[i] == 0) vis[i] = true, Q.emplace((long long)C[i], i); while(!Q.empty()) { auto [cost, idx] = Q.top(); Q.pop(); if(R[idx] == N) return printf("%lld\n", cost), 0; for(int i=0; i<M; ++i) { if(vis[i]) continue; if(XL[i] <= XR[idx] && YL[i] <= YR[idx]) { vis[i] = true; Q.emplace(cost+C[i], i); } } } puts("-1"); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3089 ms | 3576 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 4 ms | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 4 ms | 384 KB | Output is correct |
12 | Correct | 4 ms | 384 KB | Output is correct |
13 | Correct | 5 ms | 384 KB | Output is correct |
14 | Correct | 4 ms | 384 KB | Output is correct |
15 | Correct | 4 ms | 384 KB | Output is correct |
16 | Correct | 4 ms | 384 KB | Output is correct |
17 | Correct | 5 ms | 384 KB | Output is correct |
18 | Correct | 4 ms | 384 KB | Output is correct |
19 | Correct | 4 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 4 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 4 ms | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 4 ms | 384 KB | Output is correct |
12 | Correct | 4 ms | 384 KB | Output is correct |
13 | Correct | 5 ms | 384 KB | Output is correct |
14 | Correct | 4 ms | 384 KB | Output is correct |
15 | Correct | 4 ms | 384 KB | Output is correct |
16 | Correct | 4 ms | 384 KB | Output is correct |
17 | Correct | 5 ms | 384 KB | Output is correct |
18 | Correct | 4 ms | 384 KB | Output is correct |
19 | Correct | 4 ms | 384 KB | Output is correct |
20 | Correct | 86 ms | 512 KB | Output is correct |
21 | Correct | 85 ms | 632 KB | Output is correct |
22 | Correct | 124 ms | 512 KB | Output is correct |
23 | Correct | 88 ms | 564 KB | Output is correct |
24 | Correct | 14 ms | 640 KB | Output is correct |
25 | Correct | 94 ms | 712 KB | Output is correct |
26 | Correct | 85 ms | 512 KB | Output is correct |
27 | Correct | 86 ms | 512 KB | Output is correct |
28 | Correct | 17 ms | 640 KB | Output is correct |
29 | Correct | 79 ms | 512 KB | Output is correct |
30 | Correct | 8 ms | 512 KB | Output is correct |
31 | Correct | 8 ms | 640 KB | Output is correct |
32 | Correct | 8 ms | 640 KB | Output is correct |
33 | Correct | 8 ms | 640 KB | Output is correct |
34 | Correct | 105 ms | 512 KB | Output is correct |
35 | Correct | 8 ms | 640 KB | Output is correct |
36 | Correct | 7 ms | 768 KB | Output is correct |
37 | Correct | 108 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3089 ms | 3576 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |