oj.uz

답안 #970241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
970241 2024-04-26T09:10:21 Z efedmrlr 3단 점프 (JOI19_jumps) C++17
19 / 100
 523 ms 524288 KB 
#include <bits/stdc++.h>

#define int long long int
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)
#define ld long double

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 5e5 + 5;
const int INF = 1e9 + 500;
const int LGN = 20;
array<int, N> lg2;
struct RMQ {
    array<vector<int>, LGN> st;
    void reset(int s, vector<int> &arr) {
        REP(i, LGN) st[i].assign(s + 3, 0);
        for(int i = 1; i <= s; i++) {
            st[0][i] = arr[i];
        }
        for(int k = 1; k < LGN; k++) {
            for(int i = 1; i <= s; i++) {
                if(i + (1 << (k - 1)) > s) break;
                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int query(int l, int r) {
        int k = lg2[r - l + 1];
        return max(st[k][l], st[k][r - (1 << k) + 1]);
    }
};

int n, q;
vector<int> a;
RMQ st;
vector<int> res;
vector<vector<int> > ans;
void solve() {
    cin >> n;
    a.resize(n + 1, 0);
    ans.assign(n + 1, vector<int>(n + 1, 0));
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    }
    st.reset(n, a);
    for(int i = 1; i <= n; i++) {
        for(int j = i + 2; j <= n; j++) {
            int tm = (i + j) >> 1;
            ans[i][j] = st.query(i + 1, tm) + a[i] + a[j];
        }
    }
    for(int len = 3; len <= n; len++) {
        for(int i = 1; i <= n; i++) {
            int j = i + len - 1;
            if(j > n) break;
            ans[i][j] = max(ans[i][j], ans[i + 1][j]);
            ans[i][j] = max(ans[i][j], ans[i][j - 1]);
        }
    }
    cin >> q;
    REP(i, q) {
        int l, r;
        cin >> l >> r;
        cout << ans[l][r] << "\n";
    }

}

signed main() {
    lg2[1] = 0;
    for(int i = 2; i < N; i++) {
        lg2[i] = lg2[i >> 1] + 1;
    }
    fastio();
    solve();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct
11 Correct 523 ms 210772 KB Output is correct
12 Correct 357 ms 210768 KB Output is correct
13 Correct 431 ms 210628 KB Output is correct
14 Correct 425 ms 210672 KB Output is correct
15 Correct 393 ms 210772 KB Output is correct
16 Correct 385 ms 210152 KB Output is correct
17 Correct 423 ms 210260 KB Output is correct
18 Correct 423 ms 210168 KB Output is correct
19 Correct 375 ms 210764 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 215 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4188 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4476 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 2 ms 4444 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 2 ms 4452 KB Output is correct
11 Correct 523 ms 210772 KB Output is correct
12 Correct 357 ms 210768 KB Output is correct
13 Correct 431 ms 210628 KB Output is correct
14 Correct 425 ms 210672 KB Output is correct
15 Correct 393 ms 210772 KB Output is correct
16 Correct 385 ms 210152 KB Output is correct
17 Correct 423 ms 210260 KB Output is correct
18 Correct 423 ms 210168 KB Output is correct
19 Correct 375 ms 210764 KB Output is correct
20 Runtime error 215 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -