oj.uz

Submission #1096410

# Submission time Handle Problem Language Result Execution time Memory
1096410 2024-10-04T12:11:53 Z Wewoo Triple Jump (JOI19_jumps) C++17
19 / 100
 277 ms 127068 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, (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 1 ms 348 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 267 ms 126992 KB Output is correct
12 Correct 277 ms 127068 KB Output is correct
13 Correct 269 ms 127064 KB Output is correct
14 Correct 268 ms 127056 KB Output is correct
15 Correct 274 ms 127056 KB Output is correct
16 Correct 268 ms 126444 KB Output is correct
17 Correct 231 ms 126288 KB Output is correct
18 Correct 230 ms 126296 KB Output is correct
19 Correct 230 ms 126772 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 267 ms 126992 KB Output is correct
12 Correct 277 ms 127068 KB Output is correct
13 Correct 269 ms 127064 KB Output is correct
14 Correct 268 ms 127056 KB Output is correct
15 Correct 274 ms 127056 KB Output is correct
16 Correct 268 ms 126444 KB Output is correct
17 Correct 231 ms 126288 KB Output is correct
18 Correct 230 ms 126296 KB Output is correct
19 Correct 230 ms 126772 KB Output is correct
20 Incorrect 28 ms 9052 KB Output isn't correct
21 Halted 0 ms 0 KB -