Submission #245296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
245296	2020-07-06T01:19:37 Z	thecodingwizard	Pinball (JOI14_pinball)	C++11	51 / 100	1000 ms	2040 KB

pinball

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll inf = 1e18;

int main() {
    int m, n; cin >> m >> n;
    int L[m], R[m], T[m], C[m];
    for (int i = 0; i < m; i++) cin >> L[i] >> R[i] >> T[i] >> C[i];
    ll dpLeft[m], dpRight[m];
    for (int i = 0; i < m; i++) {
        dpLeft[i] = dpRight[i] = inf;

        if (L[i] == 1) dpLeft[i] = C[i];
        if (R[i] == n) dpRight[i] = C[i];

        for (int j = 0; j < i; j++) {
            if (L[i] <= T[j] && T[j] <= R[i]) {
                dpLeft[i] = min(dpLeft[i], dpLeft[j] + C[i]);
                dpRight[i] = min(dpRight[i], dpRight[j] + C[i]);
            }
        }
    }

    ll opt = inf;

    for (int i = 0; i < m; i++) {
        opt = min(opt, dpLeft[i] + dpRight[i] - C[i]);
    }

    if (opt == inf) cout << -1 << endl;
    else cout << opt << endl;

    return 0;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 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	5 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct

Subtask #2

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 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	5 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	6 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 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	5 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	6 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	6 ms	384 KB	Output is correct
17	Correct	10 ms	384 KB	Output is correct
18	Correct	9 ms	384 KB	Output is correct
19	Correct	10 ms	384 KB	Output is correct
20	Correct	9 ms	384 KB	Output is correct
21	Correct	6 ms	384 KB	Output is correct
22	Correct	8 ms	384 KB	Output is correct
23	Correct	8 ms	384 KB	Output is correct
24	Correct	8 ms	384 KB	Output is correct

Subtask #4

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	256 KB	Output is correct
3	Correct	5 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	5 ms	256 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	6 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	5 ms	384 KB	Output is correct
16	Correct	6 ms	384 KB	Output is correct
17	Correct	10 ms	384 KB	Output is correct
18	Correct	9 ms	384 KB	Output is correct
19	Correct	10 ms	384 KB	Output is correct
20	Correct	9 ms	384 KB	Output is correct
21	Correct	6 ms	384 KB	Output is correct
22	Correct	8 ms	384 KB	Output is correct
23	Correct	8 ms	384 KB	Output is correct
24	Correct	8 ms	384 KB	Output is correct
25	Correct	273 ms	888 KB	Output is correct
26	Execution timed out	1091 ms	2040 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-