Submission #933153

#	Time	Username	Problem	Language	Result	Execution time	Memory
933153		De3b0o	Triple Jump (JOI19_jumps)	C++14	0 / 100	321 ms	524288 KiB

jumps

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define er erase
#define pb push_back
#define ppb pop_back()
#define ph push
#define pp pop()
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define sqr 340
#define mod 1000000007
#define mid ((l+r)/2)

using namespace std;

ll fp(ll x , ll y)
{
    if(y==0)
        return 1;
    ll z = fp(x,y/2);
    if(y&1)
        return z*z*x;
    else
        return z*z;
}

int sqrot(ll x)
{
    int l = 0 , r = INT_MAX;
    while(l<=r)
    {
        if(mid*mid>=x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r+1;
}

ll cel(ll x , ll y)
{
    return x/y + bool(x/y);
}

string tb(ll x)
{
    string s = "";
    while(x>0)
    {
        if(x&1)
            s+='1';
        else
            s+='0';
        x/=2;
    }
    while(s.size()<60)
        s+='0';
    return s;
}

ll fb(string s)
{
    ll x = 0;
    ll c = 1;
    for(int8_t i = 0 ; 60>i ; i++)
    {
        if(s[i]=='1')
            x+=c;
        c*=2;
    }
    return x;
}

int main()
{
    d3
    ll n;
    cin >> n;
    ll a[n+1];
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i];
    ll ans[n+1][n+1];
    ll mex[n+1][n+1];
    for(int i = 1 ; n>=i ; i++)
    {
        ll mx = 0;
        for(int j = i ; n>=j ; j++)
        {
            mx=max(mx,a[j]);
            mex[i][j]=mx;
        }
    }
    for(ll i = 1 ; n>=i ; i++)
    {
        ll mx = 0;
        ll idx = 0;
        ll ans1 = 0;
        for(int j = i ; n>=j ; j++)
        {
            if(j-i+1>2)
            {
                bool e = 0;
                if(a[j]>mx)
                {
                    ans1 = ans1+a[j]-mx;
                    e=1;
                }
                if(a[j]+a[j-1]+a[j-2]>ans1)
                {
                    ans1=a[j]+a[j-1]+a[j-2];
                    e=1;
                }
                if(idx&&a[j]+mx+mex[max(i,2*idx-j)][idx-1]>ans1)
                {
                    //if(i==2&&j<6)
                        //cout << mex[max(i,2*idx-j)][idx-1] << " " << mx << " " << a[j] << "\n";
                    ans1=mx+mex[max(i,2*idx-j)][idx-1]+a[j];
                    e=1;
                }
                if(idx&&j-idx>1&&mx+a[j]+mex[idx+1][(idx+j)/2]>ans1)
                {
                    ans1=mx+a[j]+mex[idx+1][(idx+j)/2];
                    e=1;
                }
                if(e)
                {
                    idx=j;
                    mx=a[j];
                }
            }
            ans[i][j]=ans1;
        }
    }
    ll q;
    cin >> q;
    while(q--)
    {
        ll l , r;
        cin >> l >> r;
        cout << ans[l][r] << "\n";
    }
}

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