Submission #857693

#	Time	Username	Problem	Language	Result	Execution time	Memory
857693		boris_mihov	Peru (RMI20_peru)	C++17	100 / 100	105 ms	50280 KiB

peru

#include "peru.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 2500000 + 10;
const int MOD = 1e9 + 7;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, k;
int a[MAXN];
llong dp[MAXN];
std::deque <int> dq;
int fromWhere[MAXN];

struct WindowMIN
{
    std::stack <llong> right;
    std::deque <std::pair <llong,int>> left;

    void pushLeft(llong value, int idx)
    {
        while (left.size() && left.back().first > value)
        {       
            left.pop_back();
        }

        left.push_back({value, idx});
    }

    void popLeft(int idx)
    {
        if (left[0].second == idx)
        {
            left.pop_front();
        }
    }

    void pushRight(llong value)
    {
        if (right.size()) right.push(std::min(right.top(), value));
        else right.push(value);
    }

    void popRight()
    {
        while (right.empty());
        right.pop();
    }

    llong findMIN()
    {
        llong res = INF;
        if (left.size()) res = std::min(res, left[0].first);
        if (right.size()) res = std::min(res, right.top());
        return res;
    }
};

WindowMIN wMin;
int solve(int N, int K, int* v)
{
    n = N; k = K;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = v[i - 1];
    }

    a[0] = INTINF;
    dp[0] = 0;

    for (int i = 1 ; i <= n ; ++i)
    {
        if (dq.size() && dq[0] == i - k)
        {
            if (dq.size() >= 2)
            {
                fromWhere[dq[1]] = 1;
            }

            dq.pop_front();
        }

        while (dq.size() && a[i] > a[dq.back()])
        {
            if (dq.size() >= 2)
            {
                fromWhere[dq.back()] = 2;
            }

            dq.pop_back();
        }

        dq.push_back(i);
    }
    
    dq.clear();
    llong nonPopped = INF;
    for (int i = 1 ; i <= n ; ++i)
    {
        if (dq.size() && dq[0] == i - k)
        {
            if (dq.size() >= 2)
            {
                wMin.popLeft(dq[1]);
            }
            
            dq.pop_front();
        }

        while (dq.size() && a[i] > a[dq.back()])
        {
            if (dq.size() >= 2)
            {
                wMin.popRight();
            }

            dq.pop_back();
        }

        if (dq.size())
        {
            if (fromWhere[i] == 1) wMin.pushLeft(dp[dq.back()] + a[i], i);
            else if (fromWhere[i] == 2) wMin.pushRight(dp[dq.back()] + a[i]);
            else nonPopped = std::min(nonPopped, dp[dq.back()] + a[i]);
        }

        dq.push_back(i);
        dp[i] = wMin.findMIN();
        dp[i] = std::min(dp[i], nonPopped);
        dp[i] = std::min(dp[i], dp[std::max(0, i - k)] + a[dq[0]]);
    }

    int ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        ans = (1LL * ans * 23 + dp[i]) % MOD;
    }

    return ans;
}

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