Submission #773594

#TimeUsernameProblemLanguageResultExecution timeMemory
773594gagik_2007Triple Jump (JOI19_jumps)C++17
19 / 100
883 ms356356 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second ll ttt; const ll INF=1e18; const ll MOD=1e9+7; const ll N=5007; ll n,m,k; ll dp[N][N]; // l-ic r vor vercnenq maqsimumy ll pf[N][N]; // l-ic enq sksum, kamayakan r'-i hamar minchev r ll res[N][N]; // kamayakan l'-ic kamayakan r' ll a[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("output.txt","w",stdout); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } ll ans=0; for(int l=n;l>=1;l--){ for(int r=l+2;r<=n;r++){ int mid=(l+r)/2; if(r==l+2)dp[l][r]=a[l]+a[r]+a[mid]; else dp[l][r]=max(dp[l][r-1]-a[r-1]+a[r],a[l]+a[r]+a[mid]); pf[l][r]=max(pf[l][r-1],dp[l][r]); res[l][r]=max(res[l+1][r],pf[l][r]); ans=max(ans,res[l][r]); } } // for(int l=1;l<=n;l++){ // for(int r=l+2;r<=n;r++){ // cout<<dp[l][r]<<" "; // } // cout<<endl; // } // cout<<endl; // for(int l=1;l<=n;l++){ // for(int r=l+2;r<=n;r++){ // cout<<pf[l][r]<<" "; // } // cout<<endl; // } // cout<<endl; // for(int l=1;l<=n;l++){ // for(int r=l+2;r<=n;r++){ // cout<<res[l][r]<<" "; // } // cout<<endl; // } // cout<<endl; cin>>m; for(int i=0;i<m;i++){ int l,r; cin>>l>>r; cout<<res[l][r]<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...