oj.uz

Submission #1096416

# Submission time Handle Problem Language Result Execution time Memory
1096416 2024-10-04T12:15:31 Z Wewoo Triple Jump (JOI19_jumps) C++17
19 / 100
 284 ms 126740 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];
                    if (y - x == 1) continue;

                    long long ans = 0;
                    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 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 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 1 ms 860 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 860 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 860 KB Output is correct
3 Correct 1 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 1 ms 860 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 264 ms 126436 KB Output is correct
12 Correct 266 ms 126716 KB Output is correct
13 Correct 280 ms 126544 KB Output is correct
14 Correct 267 ms 126740 KB Output is correct
15 Correct 277 ms 126728 KB Output is correct
16 Correct 274 ms 125948 KB Output is correct
17 Correct 262 ms 126268 KB Output is correct
18 Correct 277 ms 126084 KB Output is correct
19 Correct 284 ms 126496 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 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 860 KB Output is correct
3 Correct 1 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 1 ms 860 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 264 ms 126436 KB Output is correct
12 Correct 266 ms 126716 KB Output is correct
13 Correct 280 ms 126544 KB Output is correct
14 Correct 267 ms 126740 KB Output is correct
15 Correct 277 ms 126728 KB Output is correct
16 Correct 274 ms 125948 KB Output is correct
17 Correct 262 ms 126268 KB Output is correct
18 Correct 277 ms 126084 KB Output is correct
19 Correct 284 ms 126496 KB Output is correct
20 Incorrect 25 ms 9052 KB Output isn't correct
21 Halted 0 ms 0 KB -