#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5 + 5 , M = 5001;
unsigned int n , p , q , rt , L[N] , R[N] , a[N] , dp[M][M] , Rt[M][M] , NRt[M][M];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1 ; i <= n ; i ++) cin >> a[i];
cin >> q;
for (int i = 1 ; i <= q ; i ++) cin >> L[i] >> R[i];
if (1LL * n * n * n / 6 * q <= 5e8){
for (int i = 1 ; i <= q ; i ++){
for (int l = L[i] ; l <= R[i] ; l ++){
for (int mid = l + 1 ; mid <= R[i] ; mid ++){
for (int r = 2 * mid - l ; r <= R[i] ; r ++)
rt = max(rt,a[l] + a[mid] + a[r]);
}
}
cout << rt << '\n';
rt = 0;
}
return 0;
}
for (int i = 1 ; i <= n ; i ++){
dp[i][i + 2] = i + 1;
for (int j = i + 3 ; j <= n ; j ++){
p = dp[i][j-1];
for (int t = p ; t - i <= j - t ; t ++) if (a[t] + a[i] + a[j] >= a[i] + a[j] + a[p])
p = t;
dp[i][j] = p;
}
return 0;
}
for (int i = 1 ; i <= n ; i ++)
for (int j = i + 2 ; j <= n ; j ++) Rt[i][j] = max(Rt[i][j - 1] , a[i] + a[j] + a[dp[i][j]]);
for (int i = n ; i ; i --)
for (int j = i - 2 ; j > 0 ; j --) NRt[j][i] = max(NRt[j+1][i] , a[i] + a[j] + a[dp[j][i]]);
memset(dp , 0 , sizeof dp);
for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
dp[i][j] = max({dp[i][j-1],dp[i+1][j] , Rt[i][j] , NRt[i][j]});
for (int i = 1 ; i <= q ; i ++){
cout << dp[L[i]][R[i]] << '\n';
}
return 0;
}
Compilation message
jumps.cpp: In function 'int main()':
jumps.cpp:15:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
15 | for (int i = 1 ; i <= n ; i ++) cin >> a[i];
| ~~^~~~
jumps.cpp:17:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
17 | for (int i = 1 ; i <= q ; i ++) cin >> L[i] >> R[i];
| ~~^~~~
jumps.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
20 | for (int i = 1 ; i <= q ; i ++){
| ~~^~~~
jumps.cpp:21:35: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
21 | for (int l = L[i] ; l <= R[i] ; l ++){
| ~~^~~~~~~
jumps.cpp:22:44: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
22 | for (int mid = l + 1 ; mid <= R[i] ; mid ++){
| ~~~~^~~~~~~
jumps.cpp:23:50: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
23 | for (int r = 2 * mid - l ; r <= R[i] ; r ++)
| ~~^~~~~~~
jumps.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
33 | for (int i = 1 ; i <= n ; i ++){
| ~~^~~~
jumps.cpp:35:32: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
35 | for (int j = i + 3 ; j <= n ; j ++){
| ~~^~~~
jumps.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
44 | for (int i = 1 ; i <= n ; i ++)
| ~~^~~~
jumps.cpp:45:32: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
45 | for (int j = i + 2 ; j <= n ; j ++) Rt[i][j] = max(Rt[i][j - 1] , a[i] + a[j] + a[dp[i][j]]);
| ~~^~~~
jumps.cpp:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
51 | for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
| ~~^~~~
jumps.cpp:51:60: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
51 | for (int i = 1 ; i <= n ; i ++) for (int j = i + 2 ; j <= n ; j ++)
| ~~^~~~
jumps.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'unsigned int' [-Wsign-compare]
54 | for (int i = 1 ; i <= q ; i ++){
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4564 KB |
Output is correct |
| 11 |
Incorrect |
52 ms |
12888 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4014 ms |
8284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4484 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4564 KB |
Output is correct |
| 11 |
Incorrect |
52 ms |
12888 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
