oj.uz

Submission #259377

# Submission time Handle Problem Language Result Execution time Memory
259377 2020-08-07T17:17:22 Z keko37 Two Antennas (JOI19_antennas) C++14
13 / 100
 152 ms 51192 KB 
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2005;

int n, q;
int h[MAXN], a[MAXN], b[MAXN];
int cost[MAXN][MAXN], dp[MAXN][MAXN], res[MAXN][MAXN];

void precompute () {
    memset(cost, -1, sizeof cost);
    memset(dp, -1, sizeof dp);
    memset(res, -1, sizeof res);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] <= j - i && j - i <= b[i] && a[j] <= j - i && j - i <= b[j]) {
                cost[i][j] = abs(h[i] - h[j]);
            }
            dp[i][j] = max(dp[i][j - 1], cost[i][j]);
        }
    }
    for (int rig = 1; rig <= n; rig++) {
        for (int lef = rig - 1; lef >= 1; lef--) {
            res[lef][rig] = max(res[lef + 1][rig], dp[lef][rig]);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
 	if (n > 2000) return 0;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }
    precompute();
    cin >> q;
    for (int i = 0; i < q; i++) {
        int lef, rig;
        cin >> lef >> rig;
        cout << res[lef][rig] << '\n';
    }
    return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47616 KB Output is correct
2 Correct 24 ms 47488 KB Output is correct
3 Correct 24 ms 47616 KB Output is correct
4 Correct 25 ms 47484 KB Output is correct
5 Correct 26 ms 47480 KB Output is correct
6 Correct 25 ms 47480 KB Output is correct
7 Correct 25 ms 47616 KB Output is correct
8 Correct 24 ms 47480 KB Output is correct
9 Correct 24 ms 47616 KB Output is correct
10 Correct 25 ms 47616 KB Output is correct
11 Correct 24 ms 47480 KB Output is correct
12 Correct 25 ms 47480 KB Output is correct
13 Correct 26 ms 47488 KB Output is correct
14 Correct 24 ms 47488 KB Output is correct
15 Correct 25 ms 47608 KB Output is correct
16 Correct 27 ms 47480 KB Output is correct
17 Correct 25 ms 47488 KB Output is correct
18 Correct 24 ms 47536 KB Output is correct
19 Correct 24 ms 47488 KB Output is correct
20 Correct 26 ms 47616 KB Output is correct
21 Correct 25 ms 47480 KB Output is correct
22 Correct 24 ms 47488 KB Output is correct
23 Correct 25 ms 47488 KB Output is correct
24 Correct 25 ms 47488 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47616 KB Output is correct
2 Correct 24 ms 47488 KB Output is correct
3 Correct 24 ms 47616 KB Output is correct
4 Correct 25 ms 47484 KB Output is correct
5 Correct 26 ms 47480 KB Output is correct
6 Correct 25 ms 47480 KB Output is correct
7 Correct 25 ms 47616 KB Output is correct
8 Correct 24 ms 47480 KB Output is correct
9 Correct 24 ms 47616 KB Output is correct
10 Correct 25 ms 47616 KB Output is correct
11 Correct 24 ms 47480 KB Output is correct
12 Correct 25 ms 47480 KB Output is correct
13 Correct 26 ms 47488 KB Output is correct
14 Correct 24 ms 47488 KB Output is correct
15 Correct 25 ms 47608 KB Output is correct
16 Correct 27 ms 47480 KB Output is correct
17 Correct 25 ms 47488 KB Output is correct
18 Correct 24 ms 47536 KB Output is correct
19 Correct 24 ms 47488 KB Output is correct
20 Correct 26 ms 47616 KB Output is correct
21 Correct 25 ms 47480 KB Output is correct
22 Correct 24 ms 47488 KB Output is correct
23 Correct 25 ms 47488 KB Output is correct
24 Correct 25 ms 47488 KB Output is correct
25 Correct 74 ms 49940 KB Output is correct
26 Correct 68 ms 47864 KB Output is correct
27 Correct 118 ms 51064 KB Output is correct
28 Correct 137 ms 51192 KB Output is correct
29 Correct 78 ms 50020 KB Output is correct
30 Correct 99 ms 49912 KB Output is correct
31 Correct 84 ms 50552 KB Output is correct
32 Correct 152 ms 51192 KB Output is correct
33 Correct 104 ms 50808 KB Output is correct
34 Correct 111 ms 49404 KB Output is correct
35 Correct 132 ms 51148 KB Output is correct
36 Correct 130 ms 51192 KB Output is correct
37 Correct 94 ms 49144 KB Output is correct
38 Correct 129 ms 50168 KB Output is correct
39 Correct 58 ms 47992 KB Output is correct
40 Correct 144 ms 50300 KB Output is correct
41 Correct 109 ms 49528 KB Output is correct
42 Correct 132 ms 50168 KB Output is correct
43 Correct 85 ms 48504 KB Output is correct
44 Correct 132 ms 50168 KB Output is correct
45 Correct 71 ms 47992 KB Output is correct
46 Correct 138 ms 50168 KB Output is correct
47 Correct 81 ms 48248 KB Output is correct
48 Correct 142 ms 50168 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47616 KB Output is correct
2 Correct 24 ms 47488 KB Output is correct
3 Correct 24 ms 47616 KB Output is correct
4 Correct 25 ms 47484 KB Output is correct
5 Correct 26 ms 47480 KB Output is correct
6 Correct 25 ms 47480 KB Output is correct
7 Correct 25 ms 47616 KB Output is correct
8 Correct 24 ms 47480 KB Output is correct
9 Correct 24 ms 47616 KB Output is correct
10 Correct 25 ms 47616 KB Output is correct
11 Correct 24 ms 47480 KB Output is correct
12 Correct 25 ms 47480 KB Output is correct
13 Correct 26 ms 47488 KB Output is correct
14 Correct 24 ms 47488 KB Output is correct
15 Correct 25 ms 47608 KB Output is correct
16 Correct 27 ms 47480 KB Output is correct
17 Correct 25 ms 47488 KB Output is correct
18 Correct 24 ms 47536 KB Output is correct
19 Correct 24 ms 47488 KB Output is correct
20 Correct 26 ms 47616 KB Output is correct
21 Correct 25 ms 47480 KB Output is correct
22 Correct 24 ms 47488 KB Output is correct
23 Correct 25 ms 47488 KB Output is correct
24 Correct 25 ms 47488 KB Output is correct
25 Correct 74 ms 49940 KB Output is correct
26 Correct 68 ms 47864 KB Output is correct
27 Correct 118 ms 51064 KB Output is correct
28 Correct 137 ms 51192 KB Output is correct
29 Correct 78 ms 50020 KB Output is correct
30 Correct 99 ms 49912 KB Output is correct
31 Correct 84 ms 50552 KB Output is correct
32 Correct 152 ms 51192 KB Output is correct
33 Correct 104 ms 50808 KB Output is correct
34 Correct 111 ms 49404 KB Output is correct
35 Correct 132 ms 51148 KB Output is correct
36 Correct 130 ms 51192 KB Output is correct
37 Correct 94 ms 49144 KB Output is correct
38 Correct 129 ms 50168 KB Output is correct
39 Correct 58 ms 47992 KB Output is correct
40 Correct 144 ms 50300 KB Output is correct
41 Correct 109 ms 49528 KB Output is correct
42 Correct 132 ms 50168 KB Output is correct
43 Correct 85 ms 48504 KB Output is correct
44 Correct 132 ms 50168 KB Output is correct
45 Correct 71 ms 47992 KB Output is correct
46 Correct 138 ms 50168 KB Output is correct
47 Correct 81 ms 48248 KB Output is correct
48 Correct 142 ms 50168 KB Output is correct
49 Incorrect 1 ms 384 KB Output isn't correct
50 Halted 0 ms 0 KB -