제출 #908118

#제출 시각아이디문제언어결과실행 시간메모리
908118arashMLG3단 점프 (JOI19_jumps)C++17
0 / 100
2283 ms9812 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int N = 2e5 + 23; const ll inf = 1e18; #define F first #define S second #define pb push_back #define sz(x) ((int)x.size()) #define kill(x) cout<<x , exit(0); #define all(x) x.begin(),x.end() #define lc (v<<1) #define rc ((v<<1)|1) #define debug(x) cerr<< #x << " : " << x << '\n'; #define int ll struct Seg { int t[N<<2]; Seg() { fill(t,t+(N<<2),0); } void upd(int pos,int x,int v=1,int tl=1,int tr= N) { if(tr-tl==1) { t[v] = max(t[v],x); return; } int mid=(tl+tr)/2; if(pos<mid) upd(pos,x,lc,tl,mid); else upd(pos,x,rc,mid,tr); t[v] = max(t[lc],t[rc]); } int get(int l,int r,int v=1,int tl=1,int tr= N) { if(l > r) return 0; if(l == tl && r == tr-1) return t[v]; int mid=(tl + tr)/2; return max(get(l,min(mid-1,r),lc,tl,mid) , get(max(l,mid),r,rc,mid,tr)); } }seg; int n,q; int a[N]; vector<int> ord; int get(int x,int y) { if(x > y)swap(x,y); if(x == y) return 0; int ans =0; if(y-x != 1) { ans = max(ans,a[x] + a[y] + seg.get(x+1,(x+y)/2)); } if(y + (y-x) <= n){ ans = max(ans, a[x] + a[y] + seg.get(y+y-x, n)); } int sex = max(x-(y-x),1LL); ans = max(ans,a[x] + a[y] + seg.get(sex,x-1)); return ans; } int32_t main() { cin>>n; for(int i = 1; i<= n ; i ++) { cin>>a[i]; seg.upd(i,a[i]); } ord.resize(n); iota(all(ord),1); sort(all(ord), [&] (int x,int y) { return a[x] > a[y]; }); vector<int> sex; int I = 0; while(sz(sex) < min(n,1000LL)) { sex.pb(ord[I++]); } reverse(all(ord)); I = 0; while(I < n && sz(sex) < 2000LL) { sex.pb(ord[I++]); } int ans=0; for(int x : sex) for(int y : sex) ans= max(ans,get(x,y)); cout<<ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...