This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i]
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;
int n, m, ans, seg[4*N];
ii a[N];
void bu(int k, int bas, int son){
if(bas == son){
seg[k] = a[bas].st;
return;
}
bu(sol, bas, orta);
bu(sag, orta + 1, son);
seg[k] = max(seg[sol], seg[sol]);
}
int qu(int k, int bas, int son, int x, int y){
if(x > y or bas > y or son < x)
return 0;
if(bas >= x and son <= y)
return seg[k];
return max(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}
int main(){
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i].st);
a[i].nd = i;
}
bu(1, 1, n);
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
m = min(n, 2000);
for(int i = 1; i <= m; i++)
for(int j = i + 1; j <= m; j++){
int bas = a[i].nd;
int son = a[j].nd;
if(bas > son)
swap(bas, son);
int mx = qu(1, 1, n, bas + 1, orta);
// cout << bas << " " << son << " " << bas + 1 << " " << orta << " = " << mx << endl;
if(bas > 1)
mx = max(mx, qu(1, 1, n, max(bas - (son - bas), 1), bas - 1));
mx = max(mx, qu(1, 1, n, son + (son - bas), n));
// if(mx + a[i].st + a[j].st == 13){
// cout << bas << " " << son << " " << mx << endl;
// }
ans = max(ans, mx + a[i].st + a[j].st);
}
printf("%d\n",ans);
return 0;
}
Compilation message (stderr)
jumps.cpp: In function 'int main()':
jumps.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
jumps.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i].st);
~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |