제출 #220784

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220784		Toirov_Sadi	3단 점프 (JOI19_jumps)	C++17	19 / 100	1489 ms	77560 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));
        }
    }
    for(int l = 2; l < n; l ++){
        for(int i = 1; i + l <= n; i ++){
            ans[i][l] = max(ans[i][l], ans[i + 1][l - 1]);
        }
    }
    cin >> q;
    while(q --){
        int l, r;
        int mx = 0;
        cin >> l >> r;
        assert(r - l + 1 >= 3);
        cout << ans[l][r - l] << "\n";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

jumps.cpp: In function 'int main()':
jumps.cpp:66:13: warning: unused variable 'mx' [-Wunused-variable]
         int mx = 0;
             ^~

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