제출 #635453

#제출 시각아이디문제언어결과실행 시간메모리
635453radal3단 점프 (JOI19_jumps)C++17
19 / 100
258 ms73688 KiB
#include <bits/stdc++.h> #pragma GCC target("sse,sse2") #pragma GCC optimize("unroll-loops,O3") #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define X first #define Y second #define all(x) (x).begin() , (x).end() #define pb push_back #define endl '\n' #define debug(x) cerr << #x << " : " << x << endl; using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pll; constexpr int N = 5e3+20,mod = 1e9+7,inf = 1e9+10,maxm = 2e5+10; inline int mkay(int a,int b){ if (a+b >= mod) return a+b-mod; if (a+b < 0) return a+b+mod; return a+b; } inline int poww(int a,int k){ if (k < 0) return 0; int z = 1; while (k){ if (k&1) z = 1ll*z*a%mod; a = 1ll*a*a%mod; k /= 2; } return z; } int n; int a[maxm],dp[N][N],mx[maxm][20],lg[N],l[maxm],r[maxm]; int rmq(int l,int r){ int j = lg[r-l]; return max(mx[r-1][j],mx[l+(1 << j)-1][j]); } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cin >> n; lg[1] = 0; rep(i,2,n+1) lg[i] = 1+lg[i/2]; if (n <= 5000){ rep(i,0,n){ cin >> a[i]; mx[i][0] = a[i]; } rep(j,1,20){ rep(i,(1 << j)-1,n){ mx[i][j] = max(mx[i][j-1],mx[i-(1 << (j-1))][j-1]); } } repr(l,n-3,0){ rep(r,l+3,n+1){ if (r-l == 3){ dp[l][r] = a[l]+a[l+1]+a[l+2]; continue; } dp[l][r] = max({dp[l+1][r],dp[l][r-1],a[l]+a[r-1]+rmq(l+1,(l+r-1)/2+1)}); } } int q; cin >> q; while (q--){ int l,r; cin >> l >> r; l--; cout << dp[l][r] << endl; } return 0; } stack<int> st; rep(i,0,n){ cin >> a[i]; mx[i][0] = a[i]; while (!st.empty() && a[st.top()] < a[i]) st.pop(); if (st.empty()) l[i] = -1; else l[i] = st.top(); st.push(i); } rep(j,1,20){ rep(i,(1 << j)-1,n){ mx[i][j] = max(mx[i][j-1],mx[i-(1 << (j-1))][j-1]); } } while(!st.empty()) st.pop(); repr(i,n-1,0){ while (!st.empty() && a[st.top()] < a[i]) st.pop(); if (st.empty()) r[i] = n; else r[i] = st.top(); st.push(i); } int q; cin >> q; const int tt = 20; while(q--){ int L,R; cin >> L >> R; L--; int ans = 0,m[tt]; memset(m,-1,sizeof m); rep(i,L,R){ rep(j,0,tt){ if (a[i] <= m[j]) continue; repr(k,tt-1,j+1) m[k] = m[k-1]; m[j] = a[i]; break; } } rep(i,L,R){ if (l[i] >= L && 2*i-l[i] < R){ if (a[i] >= m[tt-1] || a[l[i]] >= m[tt-1] || rmq(2*i-l[i],R) >= m[tt-1]) ans = max(ans,a[i]+a[l[i]]+rmq(2*i-l[i],R)); } if (r[i] < R && 2*r[i]-i < R){ if (a[i] >= m[tt-1] || a[r[i]] >= m[tt-1] || rmq(2*r[i]-i,R) >= m[tt-1]) ans = max(ans,a[i]+a[r[i]]+rmq(2*r[i]-i,R)); } } cout << ans << endl; } 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...