Submission #1295675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295675		nguyenkhangninh99	3단 점프 (JOI19_jumps)	C++20	46 / 100	587 ms	397376 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve(){
    int n; cin >> n;

    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];

    int q; cin >> q;

    if(n <= 100 && q <= 100){
        while(q--){
            int l, r; cin >> l >> r;
            int ans = 0;
            for(int i = l; i <= r; i++){
                for(int j = i + 1; j <= r; j++){
                    for(int k = j + 1; k <= r; k++){
                        if(k - j >= j - i){
                            ans = max(ans, a[i] + a[j] + a[k]);
                        }
                    }
                }
            }
            cout << ans << "\n";
        }
    }else if(n <= 5000){
        vector<vector<int>> mx(n + 1, vector<int>(n + 1)), dp(n + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++){
            mx[i][i] = a[i];
            for(int j = i + 1; j <= n; j++) mx[i][j] = max(mx[i][j - 1], a[j]);
        }

        for(int len = 2; len <= n - 1; len++){
            for(int i = 1; i + len <= n; i++){
                int j = i + len;
                int mid = (i + j) / 2;
                int L = max(1ll, i + 1), R = min(mid, j - 1);
                dp[i][j] = a[i] + mx[L][R] + a[j];
                dp[i][j] = max({dp[i][j], dp[i + 1][j], dp[i][j - 1]});
            }
        }

        while(q--){
            int l, r; cin >> l >> r;
            cout << dp[l][r] << "\n";
        }
    }else{
        vector<pair<int, int>> cand;
        vector<int> suf(n + 1);
        for(int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], a[i]);
        //nhận xét với cặp i, j. thì max[i + 1, j - 1] < min(a[i], a[j]); tìm k trên suffix max
        stack<int> st;
        for(int i = 1; i <= n; i++){
            while(!st.empty() && a[st.top()] <= a[i]){
                cand.push_back({st.top(), i});
                st.pop();
            }
            if(!st.empty()) cand.push_back({st.top(), i});
            st.push(i);
        }

        int ans = 0;
        for(auto [x, y]: cand) if(2 * y - x <= n) ans = max(ans, a[x] + a[y] + suf[2 * y - x]);
        cout << ans;
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
  
    solve();
}
 

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