Submission #857194

#	Time	Username	Problem	Language	Result	Execution time	Memory
857194		Peti	Peru (RMI20_peru)	C++17	0 / 100	0 ms	344 KiB

peru

#include <bits/stdc++.h>
#include "peru.h"

using namespace std;

const int mod = 1e9 + 7;

int solve(int N, int K, int* S){
    vector<long long> dp(N, 1e18);
    
    vector<int> nxt(N, N*2), prv(N, -N);
    for(int i = N-2; i >= 0; i--){
        nxt[i] = i+1;
        while(nxt[i] < N*2 && S[nxt[i]] <= S[i]) nxt[i] = nxt[nxt[i]];
    }
    for(int i = 1; i < N; i++){
        prv[i] = i-1;
        while(prv[i] >= 0 && S[prv[i]] <= S[i]) prv[i] = prv[prv[i]];
    }

    auto cost = [&](int x, int i) -> long long {
        if(prv[x] < i-K && i >= K) return dp[i-K] + S[x];
        return prv[x] < 0 ? S[x] : dp[prv[i]] + S[x];
    };

    stack<int> stk;
    vector<int> q(N);
    int l = 0, r = 0;
    for(int i = 0; i < N; i++){
        while(l < r && q[l] <= i-K) ++l;
        while(l < r && S[q[r-1]] <= S[i]) --r;
        while(!stk.empty() && S[stk.top()] <= S[i]) stk.pop();
        
        if(nxt[i]-prv[i] <= K){
            if(stk.empty() || cost(stk.top(), i) > cost(i, i)){
                stk.push(i);
            }
        } else {
            while(l < r && cost(q[r-1], i) >= cost(i, i)) {
                // cout << "rem: " <<  cost(q[r-1], i) << ' ' << cost(i, i) << '\n';
                --r;
            }
            q[r++] = i;
        }

        while(l+1 < r && cost(q[l], i) >= cost(q[l+1], i)) ++l;

        // cout << (stk.empty() ? "empty" : to_string(stk.top())) << '\n';
        // cout << (l == r ? -1 : q[l]) << '\n';

        dp[i] = min(!stk.empty() ? cost(stk.top(), i) : (long long)1e18, l < r ? cost(q[l], i) : (long long)1e18);
    }

    long long ans = 0;
    for(int i = 0; i < N; i++) ans = (ans * 23 + dp[i]) % mod;

    // for(long long x : dp) cout << x << ' ';
    // cout << '\n';
    // cout << ans << '\n';
    return ans;
}

// int S[(int)1e5];

// int main(){
//     int n, k;
//     cin>>n>>k;
//     for(int i = 0; i < n; i++) cin >> S[i];
//     cout << solve(n, k, S) << '\n';
//     return 0;
// }

• Subtask 1: 0 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51