oj.uz

Submission #485772

# Submission time Handle Problem Language Result Execution time Memory
485772 2021-11-09T11:08:24 Z Rainbowbunny Peru (RMI20_peru) C++17
0 / 100
 1 ms 340 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6 + 5e5 + 5;
const int mod = 1e9 + 7;

int Add(int x, int y)
{
    return x + y >= mod ? x + y - mod : x + y;
}

int Mul(int x, int y)
{
    return 1ll * x * y % mod;
}

int dp[MAXN], arr[MAXN];

int solve(int n, int k, int* v)
{
    for(int i = 1; i <= n; i++)
    {
        arr[i] = v[i - 1];
    }
    dp[0] = 0;
    deque <int> Max;
    deque <int> DP;
    for(int i = 1; i <= n; i++)
    {

        while(!Max.empty() and arr[Max.back()] <= arr[i])
        {
            Max.pop_back();
            DP.pop_back();
        }
        int curdp = Max.empty() ? 0 : Max.back();
        while(!Max.empty() and dp[DP.front()] + arr[Max.front()] >= dp[curdp] + arr[i])
        {
            Max.pop_front();
            DP.pop_front();
        }
        Max.push_back(i);
        DP.push_back(curdp);
        while(!DP.empty() and DP.front() < i - k)
        {
            if(Max.front() == DP.front() + 1)
            {
                Max.pop_back();
                DP.pop_back();
            }
            else
            {
                DP.front()++;
            }
        }
        dp[i] = arr[Max.front()] + dp[DP.front()];
    }
    int ans = 0, cur = 1;
    for(int i = n; i >= 1; i--)
    {
        ans = Add(ans, Mul(dp[i], cur));
        cur = Mul(cur, 23);
    }
    return ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -