Submission #485773

#	Time	Username	Problem	Language	Result	Execution time	Memory
485773		Rainbowbunny	Peru (RMI20_peru)	C++17	0 / 100	0 ms	340 KiB

peru

#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() = i - k;
            }
        }
        dp[i] = arr[Max.front()] + dp[DP.front()];
    }
    return 0;
    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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51