oj.uz

Submission #1096413

# Submission time Handle Problem Language Result Execution time Memory
1096413 2024-10-04T12:14:13 Z Wewoo Triple Jump (JOI19_jumps) C++17
0 / 100
 2 ms 344 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);

    freopen("CHONQUA.inp", "r", stdin);
    freopen("CHONQUA.out", "w", stdout);

    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;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:164:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |     freopen("CHONQUA.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:165:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |     freopen("CHONQUA.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 54.0

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