Submission #1168915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168915		mousebeaver	Triple Jump (JOI19_jumps)	C++20	19 / 100	2153 ms	589824 KiB

jumps

#define ll long long
#include <bits/stdc++.h>
using namespace std;

ll left(ll i)
    {return 2*i;}

ll right(ll i)
    {return 2*i+1;}

ll query(vector<ll>& s, ll i, ll a, ll b, ll l, ll r)
{
    if(l <= a && b <= r)
        return s[i];
    if(r < a || b < l)
        return 0;
    
    ll mid = (a+b)/2;
    return max(query(s, left(i), a, mid, l, r), query(s, right(i), mid+1, b, l, r));
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll& i : a)
        cin>>i;

    ll segnodes = 1;
    while(2*n > segnodes)
        segnodes *= 2;

    vector<ll> s(segnodes, 0);
    for(ll i = 0; i < n; i++)
        s[segnodes/2 + i] = a[i];
    for(ll i = segnodes/2 - 1; i > 0; i--)
        s[i] = max(s[left(i)], s[right(i)]);
    
    vector<vector<ll>> dp(n, vector<ll> (n, 0));
    for(ll i = 0; i+2 < n; i++)
        dp[i][i+2] = a[i]+a[i+1]+a[i+2];

    for(ll k = 3; k < n; k++)
    {
        for(ll i = 0; i+k < n; i++)
        {
            ll j = i+k;
            dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
            dp[i][j] = max(dp[i][j], (a[i]+a[j]+query(s, 1, 1, segnodes/2, 1+i+1, 1+i+((ll) k/2))));
        }
    }

    ll q;
    cin>>q;
    while(q--)
    {
        ll l, r;
        cin>>l>>r;
        l--; r--;
        cout<<dp[l][r]<<"\n";
    }

}

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