제출 #1297241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1297241		efeg	Peru (RMI20_peru)	C++20	100 / 100	299 ms	33888 KiB

peru

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

using i64 = long long; 

const int MOD = 1e9 + 7; 

i64 add(i64 x,i64 y){
    return (x % MOD + y % MOD) % MOD; 
}
i64 mul(i64 x,i64 y){
    return (x % MOD * (y % MOD)) % MOD; 
}


int solve(int n, int k, int* v){
    vector<i64> dp(n + 10,2e18); 
    deque<i64> dq; 
    multiset<i64> st; 

    dp[0] = v[0]; 
    dq.push_back(0); 
    for (int i = 1; i < n; i++){
        while (!dq.empty() && v[i] >= v[dq.back()]){
            int x = dq.back(); 
            dq.pop_back();  
            if (!dq.empty()) st.erase(st.find(v[x] + dp[dq.back()])); 
        }
        if (!dq.empty()) st.insert(v[i] + dp[dq.back()]); 
        dq.push_back(i);

        
        while (!dq.empty() && dq.front() <= i - k){
            int x = dq.front();
            dq.pop_front(); 
            st.erase(st.find(v[dq.front()] + dp[x])); 
        }

        //for (auto x : dq) cerr << x << ","; 
        //cerr << endl; 

        if (st.size()) dp[i] = *st.begin(); 
        if (!dq.empty()) dp[i] = min(dp[i],(i - k >= 0 ? dp[i - k] : 0) + v[dq.front()]); 
    }

    i64 pw = 1,ans = 0; 
    for (int i = n-1; i > -1; i--){
        ans = add(ans,mul(dp[i],pw));
        pw = mul(pw,23); 
    }

    /*for (int i = 0; i < n; i++){
        cerr << dp[i] << " "; 
    }*/ 


    return ans; 
}

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