oj.uz

Submission #1096414

# Submission time Handle Problem Language Result Execution time Memory
1096414 2024-10-04T12:14:27 Z Wewoo Triple Jump (JOI19_jumps) C++17
19 / 100
 303 ms 125092 KB 
#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 + 1, (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
            Sub3::Solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 238 ms 125048 KB Output is correct
12 Correct 236 ms 125092 KB Output is correct
13 Correct 233 ms 124756 KB Output is correct
14 Correct 260 ms 124876 KB Output is correct
15 Correct 270 ms 124756 KB Output is correct
16 Correct 303 ms 124392 KB Output is correct
17 Correct 267 ms 124244 KB Output is correct
18 Correct 262 ms 124152 KB Output is correct
19 Correct 275 ms 124752 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 8372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 860 KB Output is correct
11 Correct 238 ms 125048 KB Output is correct
12 Correct 236 ms 125092 KB Output is correct
13 Correct 233 ms 124756 KB Output is correct
14 Correct 260 ms 124876 KB Output is correct
15 Correct 270 ms 124756 KB Output is correct
16 Correct 303 ms 124392 KB Output is correct
17 Correct 267 ms 124244 KB Output is correct
18 Correct 262 ms 124152 KB Output is correct
19 Correct 275 ms 124752 KB Output is correct
20 Incorrect 27 ms 8372 KB Output isn't correct
21 Halted 0 ms 0 KB -