Submission #848893

#	Time	Username	Problem	Language	Result	Execution time	Memory
848893		TheSahib	Peru (RMI20_peru)	C++17	100 / 100	396 ms	59160 KiB

peru

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "peru.h"

#define ll long long
#define pii pair<int, int>

using namespace std;

const int MAX = 25e5 + 5;
const ll oo = 1e18 + 9;
const int mod = 1e9 + 7;

ll dp[MAX];
int* arr;

multiset<ll> st;
deque<int> q;

void erase_front(){
    if(q.size() >= 2){
        int a = q[0];
        int b = q[1];
        st.erase(st.find(dp[b] + arr[a]));
    }
    q.pop_front();
}

void erase_back(){
    int a = q[q.size() - 1];
    int b = q[q.size() - 2];
    st.erase(st.find(dp[a] + arr[b]));
    q.pop_back();
}

void insert(int a){
    q.push_front(a);
    if(q.size() > 1){
        int b = q[1];
        st.insert(dp[b] + arr[a]);
    }
}

int solve(int n, int k, int* v){
    arr = v;
    q.push_front(0);
    dp[0] = arr[0];

    for (int i = 1; i < k; i++)
    {
        while(q.size() && arr[q.front()] <= arr[i]){
            erase_front();
        }
        insert(i);
        
        dp[i] = arr[q.back()];
    }
    
    
    for (int i = k; i < n; i++)
    {
        while(q.size() && arr[q.front()] <= arr[i]){
            erase_front();
        }
        insert(i);

        if(q.back() + k - 1 < i){
            erase_back();
        }

        dp[i] = dp[i - k] + arr[q.back()];
        if(st.size()){
            dp[i] = min(dp[i], *st.begin());
        }
    }
    ll ans = 0;
    for (int i = 0; i <= n - 1; i++)
    {
        ans = (ans * 23 + dp[i]) % mod;
    }
    return ans;
}

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