Submission #615447

#	Time	Username	Problem	Language	Result	Execution time	Memory
615447		AbdelmagedNour	Triple Jump (JOI19_jumps)	C++17	46 / 100	369 ms	73240 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int sp[20][N],dp[5005][5005];
void build(int n){
    for(int j=1;j<20;j++){
        for(int i=0;i+(1<<j)<=n;i++){
            sp[j][i]=max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
        }
    }
}
int RMQ(int l,int r){
    int sz=__lg(r-l+1);
    return max(sp[sz][l],sp[sz][r-(1<<sz)+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,ans=0;
    cin>>n;
    for(int i=0;i<n;i++)cin>>sp[0][i];
    build(n);
    if(n<=5000){
        for(int sz=2;sz<n;sz++){
            for(int i=0;i+sz<n;i++){
                dp[i][i+sz]=sp[0][i]+sp[0][i+sz]+RMQ(i+1,(i+sz+i)/2);
                dp[i][i+sz]=max({dp[i][i+sz],dp[i+1][i+sz],dp[i][i+sz-1]});
            }
        }
        ans=dp[0][n-1];
    }else{
        vector<pair<int,int>>seg;
        vector<int>st;// decreasing stack
        for(int i=0;i<n;i++){
            while(!st.empty()&&sp[0][i]>=sp[0][st.back()]){
                seg.push_back({st.back(),i});
                st.pop_back();
            }
            if(!st.empty())seg.push_back({st.back(),i});
            st.push_back(i);
        }
        sort(seg.begin(),seg.end());
        for(int i=0;i<seg.size();i++){
            int l=seg[i].first,r=seg[i].second;
            if(2*r-l<n)ans=max(ans,sp[0][l]+sp[0][r]+RMQ(2*r-l,n-1));
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;r--;
        if(l==0&&r==n-1)cout<<ans<<"\n";
        else cout<<dp[l][r]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i=0;i<seg.size();i++){
      |                     ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54