Submission #849401

#	Time	Username	Problem	Language	Result	Execution time	Memory
849401		TahirAliyev	Peru (RMI20_peru)	C++17	100 / 100	261 ms	73556 KiB

peru

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

#define ll long long
#define oo 1e17
#define pii pair<int, int>

using namespace std;

const int MAX = 25e5 + 5, MOD = 1e9 + 7;
ll arr[MAX];
ll dp[MAX];
ll val[MAX];
priority_queue<pair<ll, int>> s;
bool d[MAX];
deque<int> dq;

void clearQ(){
    while(d[s.top().second]){
        s.pop();
    }
}

int solve(int n, int k, int* v){
    for(int i = 0; i < n; i++){
        arr[i + 1] = v[i];
    }
    dq.push_back(1);
    dp[1] = arr[1];
    for(int i = 2; i <= n; i++){
        while(dq.size() && arr[dq.back()] <= arr[i]){
            if(dq.size() > 1) d[dq.back()] = 1;
            dq.pop_back();
        }
        if(dq.size() && dq.front() == i - k){
            dq.pop_front();
            if(dq.size()){
                d[dq.front()] = 1;
            }
        }
        dp[i] = oo;
        if(dq.size()){
            val[i] = dp[dq.back()] + arr[i];
            s.push({-val[i], i});
            clearQ();
            dp[i] = -s.top().first;
        }
        dq.push_back(i);
        dp[i] = min(dp[i], arr[dq.front()] + dp[max(0, i - k)]);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans *= 23;
        ans += dp[i];
        ans %= MOD;
    }
    return ans;
}

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