Submission #1092699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092699		alexdd	Peru (RMI20_peru)	C++17	100 / 100	532 ms	79840 KiB

peru

#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
const long long INF = 1e18;
long long a[2500005];
long long dp[2500005];
multiset<long long> s;
int solve(int n, int k, int* v)
{
    a[0]=2e9+2;
    deque<pair<long long,long long>> dq;///{poz,mxm}
    deque<int> sw;
    dq.push_back({0,0});
    s.insert(0);
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
        while(!sw.empty() && sw.front() <= i-k)
            sw.pop_front();
        while(!sw.empty() && a[sw.back()] <= a[i])
            sw.pop_back();
        sw.push_back(i);

        dp[i]=INF;
        dp[i] = min(dp[i], dp[max(0,i-k)]+a[sw.front()]);
        while(!dq.empty() && dq.front().first < i-k)
        {
            s.erase(s.find(dp[dq.front().first]+dq.front().second));
            dq.pop_front();
        }
        int ult=-1;
        while(!dq.empty() && a[i] > dq.back().second)
        {
            ult = dq.back().first;
            s.erase(s.find(dp[dq.back().first]+dq.back().second));
            dq.pop_back();
        }
        if(ult!=-1)
        {
            dq.push_back({ult,a[i]});
            s.insert(dp[ult]+a[i]);
        }
        if(!s.empty()) dp[i] = min(dp[i], *s.begin());
        dq.push_back({i,0});
        s.insert(dp[i]);
    }

    long long rez=0,put23=1;
    for(int i=n;i>0;i--)
    {
        rez = (rez + dp[i]%MOD*put23)%MOD;
        put23 = put23*23LL%MOD;
    }
    return rez;
}
/*
8 3
3 2 9 8 7 11 3 4
*/

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