#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)3e3+10;
int n,q,l,r,a[mxN], b[mxN],h[mxN], dp[mxN][mxN];
int compatible(int i, int j){
if(abs(i-j)>=max(a[i],a[j]) and abs(i-j)<=min(b[i],b[j]))
return abs(h[i]-h[j]);
return -1;
}
int main(){
cin >> n; memset(dp,-1,sizeof(dp));
for(int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
for(int i = 1; i <= n; i++)
for(int j = i+1; j <= n; j++)
dp[i][j] = compatible(i,j);
for(int l = 2; l <= n; l++){
for(int i = 1, j=i+l-1; j <= n; i++,j++){
dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
dp[i-1][j] = max(dp[i-1][j],dp[i][j]);
}
}
cin >> q;while(q--) cin>>l>>r,cout<<dp[l][r]<<"\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
35668 KB |
Output is correct |
2 |
Correct |
13 ms |
35672 KB |
Output is correct |
3 |
Correct |
14 ms |
35768 KB |
Output is correct |
4 |
Correct |
13 ms |
35768 KB |
Output is correct |
5 |
Correct |
12 ms |
35668 KB |
Output is correct |
6 |
Correct |
12 ms |
35760 KB |
Output is correct |
7 |
Correct |
12 ms |
35668 KB |
Output is correct |
8 |
Correct |
12 ms |
35688 KB |
Output is correct |
9 |
Correct |
13 ms |
35668 KB |
Output is correct |
10 |
Correct |
11 ms |
35668 KB |
Output is correct |
11 |
Correct |
11 ms |
35736 KB |
Output is correct |
12 |
Correct |
12 ms |
35728 KB |
Output is correct |
13 |
Correct |
14 ms |
35668 KB |
Output is correct |
14 |
Correct |
12 ms |
35744 KB |
Output is correct |
15 |
Correct |
11 ms |
35772 KB |
Output is correct |
16 |
Correct |
16 ms |
35668 KB |
Output is correct |
17 |
Correct |
12 ms |
35668 KB |
Output is correct |
18 |
Correct |
13 ms |
35708 KB |
Output is correct |
19 |
Correct |
12 ms |
35712 KB |
Output is correct |
20 |
Correct |
14 ms |
35764 KB |
Output is correct |
21 |
Correct |
12 ms |
35668 KB |
Output is correct |
22 |
Correct |
15 ms |
35668 KB |
Output is correct |
23 |
Correct |
14 ms |
35668 KB |
Output is correct |
24 |
Correct |
16 ms |
35732 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
35668 KB |
Output is correct |
2 |
Correct |
13 ms |
35672 KB |
Output is correct |
3 |
Correct |
14 ms |
35768 KB |
Output is correct |
4 |
Correct |
13 ms |
35768 KB |
Output is correct |
5 |
Correct |
12 ms |
35668 KB |
Output is correct |
6 |
Correct |
12 ms |
35760 KB |
Output is correct |
7 |
Correct |
12 ms |
35668 KB |
Output is correct |
8 |
Correct |
12 ms |
35688 KB |
Output is correct |
9 |
Correct |
13 ms |
35668 KB |
Output is correct |
10 |
Correct |
11 ms |
35668 KB |
Output is correct |
11 |
Correct |
11 ms |
35736 KB |
Output is correct |
12 |
Correct |
12 ms |
35728 KB |
Output is correct |
13 |
Correct |
14 ms |
35668 KB |
Output is correct |
14 |
Correct |
12 ms |
35744 KB |
Output is correct |
15 |
Correct |
11 ms |
35772 KB |
Output is correct |
16 |
Correct |
16 ms |
35668 KB |
Output is correct |
17 |
Correct |
12 ms |
35668 KB |
Output is correct |
18 |
Correct |
13 ms |
35708 KB |
Output is correct |
19 |
Correct |
12 ms |
35712 KB |
Output is correct |
20 |
Correct |
14 ms |
35764 KB |
Output is correct |
21 |
Correct |
12 ms |
35668 KB |
Output is correct |
22 |
Correct |
15 ms |
35668 KB |
Output is correct |
23 |
Correct |
14 ms |
35668 KB |
Output is correct |
24 |
Correct |
16 ms |
35732 KB |
Output is correct |
25 |
Correct |
229 ms |
38080 KB |
Output is correct |
26 |
Correct |
44 ms |
35988 KB |
Output is correct |
27 |
Correct |
329 ms |
39264 KB |
Output is correct |
28 |
Correct |
354 ms |
39348 KB |
Output is correct |
29 |
Correct |
227 ms |
38140 KB |
Output is correct |
30 |
Correct |
231 ms |
38068 KB |
Output is correct |
31 |
Correct |
283 ms |
38672 KB |
Output is correct |
32 |
Correct |
310 ms |
39308 KB |
Output is correct |
33 |
Correct |
289 ms |
38980 KB |
Output is correct |
34 |
Correct |
159 ms |
37432 KB |
Output is correct |
35 |
Correct |
305 ms |
39448 KB |
Output is correct |
36 |
Correct |
312 ms |
39336 KB |
Output is correct |
37 |
Correct |
181 ms |
37196 KB |
Output is correct |
38 |
Correct |
299 ms |
38380 KB |
Output is correct |
39 |
Correct |
61 ms |
36140 KB |
Output is correct |
40 |
Correct |
312 ms |
38344 KB |
Output is correct |
41 |
Correct |
224 ms |
37604 KB |
Output is correct |
42 |
Correct |
307 ms |
38332 KB |
Output is correct |
43 |
Correct |
120 ms |
36672 KB |
Output is correct |
44 |
Correct |
304 ms |
38396 KB |
Output is correct |
45 |
Correct |
69 ms |
36172 KB |
Output is correct |
46 |
Correct |
313 ms |
38396 KB |
Output is correct |
47 |
Correct |
95 ms |
36404 KB |
Output is correct |
48 |
Correct |
300 ms |
38300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
72408 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
35668 KB |
Output is correct |
2 |
Correct |
13 ms |
35672 KB |
Output is correct |
3 |
Correct |
14 ms |
35768 KB |
Output is correct |
4 |
Correct |
13 ms |
35768 KB |
Output is correct |
5 |
Correct |
12 ms |
35668 KB |
Output is correct |
6 |
Correct |
12 ms |
35760 KB |
Output is correct |
7 |
Correct |
12 ms |
35668 KB |
Output is correct |
8 |
Correct |
12 ms |
35688 KB |
Output is correct |
9 |
Correct |
13 ms |
35668 KB |
Output is correct |
10 |
Correct |
11 ms |
35668 KB |
Output is correct |
11 |
Correct |
11 ms |
35736 KB |
Output is correct |
12 |
Correct |
12 ms |
35728 KB |
Output is correct |
13 |
Correct |
14 ms |
35668 KB |
Output is correct |
14 |
Correct |
12 ms |
35744 KB |
Output is correct |
15 |
Correct |
11 ms |
35772 KB |
Output is correct |
16 |
Correct |
16 ms |
35668 KB |
Output is correct |
17 |
Correct |
12 ms |
35668 KB |
Output is correct |
18 |
Correct |
13 ms |
35708 KB |
Output is correct |
19 |
Correct |
12 ms |
35712 KB |
Output is correct |
20 |
Correct |
14 ms |
35764 KB |
Output is correct |
21 |
Correct |
12 ms |
35668 KB |
Output is correct |
22 |
Correct |
15 ms |
35668 KB |
Output is correct |
23 |
Correct |
14 ms |
35668 KB |
Output is correct |
24 |
Correct |
16 ms |
35732 KB |
Output is correct |
25 |
Correct |
229 ms |
38080 KB |
Output is correct |
26 |
Correct |
44 ms |
35988 KB |
Output is correct |
27 |
Correct |
329 ms |
39264 KB |
Output is correct |
28 |
Correct |
354 ms |
39348 KB |
Output is correct |
29 |
Correct |
227 ms |
38140 KB |
Output is correct |
30 |
Correct |
231 ms |
38068 KB |
Output is correct |
31 |
Correct |
283 ms |
38672 KB |
Output is correct |
32 |
Correct |
310 ms |
39308 KB |
Output is correct |
33 |
Correct |
289 ms |
38980 KB |
Output is correct |
34 |
Correct |
159 ms |
37432 KB |
Output is correct |
35 |
Correct |
305 ms |
39448 KB |
Output is correct |
36 |
Correct |
312 ms |
39336 KB |
Output is correct |
37 |
Correct |
181 ms |
37196 KB |
Output is correct |
38 |
Correct |
299 ms |
38380 KB |
Output is correct |
39 |
Correct |
61 ms |
36140 KB |
Output is correct |
40 |
Correct |
312 ms |
38344 KB |
Output is correct |
41 |
Correct |
224 ms |
37604 KB |
Output is correct |
42 |
Correct |
307 ms |
38332 KB |
Output is correct |
43 |
Correct |
120 ms |
36672 KB |
Output is correct |
44 |
Correct |
304 ms |
38396 KB |
Output is correct |
45 |
Correct |
69 ms |
36172 KB |
Output is correct |
46 |
Correct |
313 ms |
38396 KB |
Output is correct |
47 |
Correct |
95 ms |
36404 KB |
Output is correct |
48 |
Correct |
300 ms |
38300 KB |
Output is correct |
49 |
Runtime error |
41 ms |
72408 KB |
Execution killed with signal 11 |
50 |
Halted |
0 ms |
0 KB |
- |