Submission #1240938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240938		chikien2009	Triple Jump (JOI19_jumps)	C++20	19 / 100	252 ms	122716 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, q, a, b, c, sp[20][500000];
long long res, pre[5000][5000];

inline int Get(int l, int r)
{
    int k = __lg(r - l + 1);
    return max(sp[k][l], sp[k][r - (1 << k) + 1]);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> sp[0][i];
    }
    for (int i = 1; i <= __lg(n); ++i)
    {
        for (int j = 0; j + (1 << i) <= n; ++j)
        {
            sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
        }
    }
    if (n <= 5000)
    {
        for (int x = 2; x < n; ++x)
        {
            for (int i = 0, j = x; j < n; ++i, ++j)
            {
                pre[i][j] = sp[0][i] + sp[0][j] + Get(i + 1, (i + j) / 2);
                pre[i][j] = max({pre[i][j], pre[i + 1][j], pre[i][j - 1]});
            }
        }
    }
    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        a--;
        b--;
        if (n <= 5000)
        {
            cout << pre[a][b] << "\n";
        }
    }
    return 0;
}

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