oj.uz

Submission #773887

# Submission time Handle Problem Language Result Execution time Memory
773887 2023-07-05T09:18:40 Z CyberCow Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 203160 KB 
//#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const int N = 5005;
int a[200005];
int dp[N][N];
int s[4 * 200005];

void build(int p, int lp, int rp)
{
    if (lp == rp)
    {
        s[p] = a[lp];
        return;
    }
    int m = (lp + rp) / 2;
    build(p * 2, lp, m);
    build(p * 2 + 1, m + 1, rp);
    s[p] = max(s[p * 2], s[p * 2 + 1]);
}

int get(int p, int lp, int rp, int l, int r)
{
    if (l > r)
        return 0;
    if (lp == l && rp == r)
        return s[p];
    int m = (lp + rp) / 2;
    return max(get(p * 2, lp, m, l, min(r, m)), get(p * 2 + 1, m + 1, rp, max(m + 1, l), r));
}

void solve()
{
    int n, i, j, x, y, m;
    cin >> n;
    if (n <= 5000)
    {
        for (i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        build(1, 1, n);
        for (i = 1; i <= n; i++)
        {
            int ma = 0;
            for (j = i + 2; j <= n; j++)
            {
                dp[i][j] = max(dp[i][j], get(1, 1, n, i + 1, (i + j) / 2) + a[i] + a[j]);
            }
        }
        for (i = 2; i <= n; i++)
        {
            for (j = 1; j <= n; j++)
            {
                dp[j][j + i - 1] = max(dp[j][j + i - 1], max(dp[j + 1][j + i - 1], dp[j][j + i - 2]));
            }
        }
        int q;
        cin >> q;
        for (i = 0; i < q; i++)
        {
            cin >> x >> y;
            cout << dp[x][y] << '\n';
        }
    }
    else
    {
        vector<pair<int, int>> v;
        vector<pair<int, pair<int, int>>>ss;
        for ( i = 1; i <= n; i++)
        {
            cin >> a[i];
            v.push_back({ a[i], i });
        }
        int q, xx, yy;
        cin >> q >> xx >> yy;
        build(1, 1, n);
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        for ( i = 0; i < min(1500, n); i++)
        {
            for ( j = i + 1; j < min(7000, n); j++)
            {
                ss.push_back({ v[i].first + v[j].first, {min(v[i].second, v[j].second), max(v[i].second, v[j].second)} });
            }
        }
        sort(ss.begin(), ss.end());
        int ans = 0;
        for (i = 0; i < ss.size(); i++)
        {
            int l = ss[i].second.first, r = ss[i].second.second;
            ans = max(ans, a[l] + a[r] + get(1, 1, n, l + 1, r - 1));
            ans = max(ans, a[l] + a[r] + get(1, 1, n, max(1, l - (r - l)), l - 1));
            ans = max(ans, a[l] + a[r] + get(1, 1, n, r + (r - l), n));
        }
        cout << ans;
    }
}


int main() {    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message

jumps.cpp: In function 'void solve()':
jumps.cpp:69:17: warning: unused variable 'ma' [-Wunused-variable]
   69 |             int ma = 0;
      |                 ^~
jumps.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for (i = 0; i < ss.size(); i++)
      |                     ~~^~~~~~~~~~~
jumps.cpp:58:24: warning: unused variable 'm' [-Wunused-variable]
   58 |     int n, i, j, x, y, m;
      |                        ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 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 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1921 ms 103272 KB Output is correct
12 Correct 1985 ms 103312 KB Output is correct
13 Correct 1911 ms 103320 KB Output is correct
14 Correct 1928 ms 103364 KB Output is correct
15 Correct 1935 ms 103388 KB Output is correct
16 Correct 1950 ms 102644 KB Output is correct
17 Correct 1969 ms 102676 KB Output is correct
18 Correct 1894 ms 102616 KB Output is correct
19 Correct 1914 ms 103364 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 203160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1921 ms 103272 KB Output is correct
12 Correct 1985 ms 103312 KB Output is correct
13 Correct 1911 ms 103320 KB Output is correct
14 Correct 1928 ms 103364 KB Output is correct
15 Correct 1935 ms 103388 KB Output is correct
16 Correct 1950 ms 102644 KB Output is correct
17 Correct 1969 ms 102676 KB Output is correct
18 Correct 1894 ms 102616 KB Output is correct
19 Correct 1914 ms 103364 KB Output is correct
20 Execution timed out 4067 ms 203160 KB Time limit exceeded
21 Halted 0 ms 0 KB -