제출 #677691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677691		Cross_Ratio	3단 점프 (JOI19_jumps)	C++14	19 / 100	4082 ms	127216 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct SegTree {
    vector<int> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void cons() {
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i] = max(seg[2*i], seg[2*i+1]);
        }
    }
    int sum(int s, int e, int n, int ns, int ne) {
        if(e<=ns||ne<=s) return 0;
        if(s<=ns&&ne<=e) return seg[n];
        int mid = ns + ne >> 1;
        return max(sum(s, e, 2*n, ns, mid), sum(s, e, 2*n+1, mid, ne));
    }
};
int A[500005];
int B[5005][5005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    int i, j;
    for(i=0;i<N;i++) cin >> A[i];
    SegTree tree(N);
    int MAX = tree.MAX;
    for(i=0;i<N;i++) tree.seg[i+MAX/2] = A[i];
    tree.cons();
    for(int l = 0; l < N; l++) {
        for(int r = l + 2; r < N; r++) {
            B[l][r] = A[l]+A[r]+tree.sum(l+1, (l+r)/2+1, 1, 0, MAX/2);
        }
    }
    for(int len = 3; len <= N-1; len++) {
        for(i=0;i+len<=N-1;i++) {
            B[i][i+len] = max(B[i][i+len], B[i+1][i+len]);
            B[i][i+len] = max(B[i][i+len], B[i][i+len-1]);
        }
    }
    int Q;
    cin >> Q;
    while(Q--) {
        int l, r;
        cin >> l >> r;
        cout << B[l-1][r-1] << '\n';
    }
}

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

jumps.cpp: In member function 'long long int SegTree::sum(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:21:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:33:12: warning: unused variable 'j' [-Wunused-variable]
   33 |     int i, j;
      |            ^

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