oj.uz

Submission #857627

# Submission time Handle Problem Language Result Execution time Memory
857627 2023-10-06T14:32:29 Z boris_mihov Peru (RMI20_peru) C++17
0 / 100
 6 ms 12888 KB 
#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::stack <int> st;
std::deque <int> dq;
std::multiset <int> 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;
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (st.size() && a[st.top()] <= a[i])
        {
            st.pop();
        }

        prev[i] = st.top();
        st.push(i);
    }
 
    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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 12888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 12888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 12888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -