Submission #220783

#	Time	Username	Problem	Language	Result	Execution time	Memory
220783		Toirov_Sadi	Triple Jump (JOI19_jumps)	C++17	5 / 100	4073 ms	71240 KiB

jumps

#include <bits/stdc++.h>

#define FILE
#define fr first
#define se second

using namespace std;

const long long M = 21;
const long long N = 5e3 + 7;
const long long inf = 1e9 + 7;
const long long mod = 1e9 + 7;

int n;
int q;
int a[N];
int lg[N];
int d[N][M];
int ans[N][N];
int get(int l, int r){
    if(l > r){
        return 0;
    }
    int h = (r - l + 1);
    return max(d[l][lg[h]], d[r - (1 << lg[h]) + 1][lg[h]]);
}
int main()
{
    #ifdef FILEs
        freopen("input.txt", "r", stdin);
        /// freopen("output.txt", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        d[i][0] = a[i];
    }
    lg[2] = 1;
    for(int i = 3; i < N; i ++){
        lg[i] = lg[i / 2] + 1;
    }
    for(int j = 1; j < M; j ++){
        for(int i = 1; i + (1 << j) - 1 <= n; i ++){
            d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int l = 2; l <= n; l ++){
        /// cout << "length: " << l << ":\n";
        for(int i = 1; i + l <= n; i ++){
            /// cout << "\t" << i << " (" << i + 1 << ", " << (2 * i + l) / 2 << ") " << i + l << "\n";
            /// cout << "\t" << a[i] << " " << get(i + 1, (2 * i + l) / 2) << " " << a[i + l] << "\n";
            ans[i][l] = max(ans[i][l - 1], a[i] + a[i + l] + get(i + 1, (2 * i + l)/ 2));
        }
    }
    cin >> q;
    while(q --){
        int l, r;
        int mx = 0;
        cin >> l >> r;
        assert(r - l + 1 >= 3);
        for(int i = 0; i <= n; i ++){
            if(l + i > n || r - l - i <= 1){
                break;
            }
            mx = max(mx, ans[l + i][r - l - i]);
        }
        cout << mx << "\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54