Submission #1295663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295663		nguyenkhangninh99	3단 점프 (JOI19_jumps)	C++20	19 / 100	596 ms	397420 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";
        }
    }
}
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: 0 / 27
• Subtask 4: 0 / 54