Submission #1096411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096411		Wewoo	Triple Jump (JOI19_jumps)	C++17	19 / 100	4065 ms	124752 KiB

jumps

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

const int MAXN = 5e5 + 105;

int n;
int a[MAXN + 5];
int m, l, r;

namespace Sub1
{
    long long dp[505][505];
    void Solve()
    {
        for (int i = 1; i <= n - 2; ++i)
        {
            for (int j = i + 2; j <= n; ++j)
            {
                for (int z = i + 1; z <= j - 1; ++z)
                    if (z - i <= j - z) dp[i][j] = max(dp[i][j], 1LL * a[z]); else break;

                dp[i][j] += a[i] + a[j];
            }
        }

        for (int len = 4; len <= n; ++len)
        {
            for (int l = 1; l <= n - len + 1; ++l)
            {
                int r = l + len - 1;
                dp[l][r] = max(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
            }
        }

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

namespace Sub2
{
    long long dp[5005][5005];
    void Solve()
    {
        for (int i = 1; i <= n - 2; ++i)
        {
            int Max = 0;
            for (int j = i + 2; j <= n; ++j)
            {
                Max = max(Max, a[(i + j) / 2]);
                dp[i][j] = a[i] + Max + a[j];
            }
        }

        for (int len = 4; len <= n; ++len)
        {
            for (int l = 1; l <= n - len + 1; ++l)
            {
                int r = l + len - 1;
                dp[l][r] = max(dp[l][r], max(dp[l + 1][r], dp[l][r - 1]));
            }
        }

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

namespace Sub3
{
    struct Data
    {
        int val[3];
    } tree[4 * MAXN + 20];

    bool cmp(const int &x, const int &y)
    {
        return a[x] > a[y];
    }

    vector <int> v;
    void combine(Data a, Data b, Data &c)
    {
        for (int i = 0; i < 3; ++i) v.push_back(a.val[i]), v.push_back(b.val[i]);
        sort(v.begin(), v.end(), cmp);
        for (int i = 0; i < 3; ++i) c.val[i] = v[i];
        v.clear();
    }

    void buildTree(int id, int l, int r)
    {
        if (l == r)
        {
            tree[id].val[0] = l;
            return;
        }

        int mid = (l + r) / 2;
        buildTree(id * 2, l, mid);
        buildTree(id * 2 + 1, mid + 1, r);

        combine(tree[id * 2], tree[id * 2 + 1], tree[id]);
    }

    Data getSet(int id, int l, int r, const int &u, const int &v)
    {
        if (l > v || r < u) return tree[0];
        if (u <= l && r <= v) return tree[id];

        int mid = (l + r) / 2;
        Data ans, L = getSet(id * 2, l, mid, u, v), R = getSet(id * 2 + 1, mid + 1, r, u, v);
        combine(L, R, ans);
        return ans;
    }

    int getMax(int id, int l, int r, const int &u, const int &v)
    {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return tree[id].val[0];

        int mid = (l + r) / 2;
        return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v));
    }

    void Solve()
    {
        buildTree(1, 1, n);

        while (m --)
        {
            cin >> l >> r;
            Data temp = getSet(1, 1, n, l, r);
            sort(temp.val, temp.val + 3);

            long long res = 0;
            for (int i = 0; i < 3; ++i)
                for (int j = i + 1; j < 3; ++j)
                {
                    int x = temp.val[i], y = temp.val[j];
                    long long ans = 0;
                    if (y - x > 1) ans = max(ans, 1LL * getMax(1, 1, n, x, (x + y) / 2));
                    if (x > l) ans = max(ans, 1LL * getMax(1, 1, n, max(l, x - (y - x)), x - 1));
                    if (y + (y - x) <= r) ans = max(ans, 1LL * getMax(1, 1, n, y + (y - x), r));
                    res = max(res, ans + a[x] + a[y]);
                }

            cout << res << "\n";
        }
    }
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m;
    if (n <= 500) Sub1::Solve(); else
        if (n <= 5000) Sub2::Solve(); else
        while (true) {};

    return 0;
}

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