oj.uz

Submission #485776

# Submission time Handle Problem Language Result Execution time Memory
485776 2021-11-09T11:15:58 Z Rainbowbunny Peru (RMI20_peru) C++17
0 / 100
 0 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;
}
 
long long 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() ? max(0, i - k) : 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()];
    }
    int ans = 0, cur = 1;
    for(int i = n; i >= 1; i--)
    {
        dp[i] %= mod;
        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 0 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 0 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 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -