Submission #857628

#	Time	Username	Problem	Language	Result	Execution time	Memory
857628		boris_mihov	Peru (RMI20_peru)	C++17	100 / 100	331 ms	70332 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;
std::multiset <llong> ms;
int prev[MAXN];

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)
            {
                ms.erase(ms.find(a[dq[1]] + dp[dq[0]]));
            }

            dq.pop_front();
        }

        while (dq.size() && a[i] > a[dq.back()])
        {
            if (dq.size() >= 2)
            {
                ms.erase(ms.find(a[dq.back()] + dp[dq[dq.size() - 2]]));
            }

            dq.pop_back();
        }

        if (dq.size())
        {
            ms.insert(dp[dq.back()] + a[i]);
        }

        dq.push_back(i);
        dp[i] = INF;
        if (ms.size()) dp[i] = (*ms.begin());
        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