oj.uz

Submission #872599

# Submission time Handle Problem Language Result Execution time Memory
872599 2023-11-13T12:33:54 Z 12345678 Peru (RMI20_peru) C++17
0 / 100
 1 ms 348 KB 
#include "peru.h"
#include <bits/stdc++.h>

using namespace std;

const int mod=1e9+7;

int solve(int n, int k, int* v){
    vector<long long> dp(n+1), p(n+1);
    long long res=0;
    p[0]=1;
    for (int i=1; i<=n; i++) p[i]=(p[i-1]*23)%mod;
    for (int i=1; i<=n; i++)
    {
        int mx=0;
        dp[i]=LLONG_MAX;
        for (int j=i; j>=max(i-k+1, 1); j--)
        {
            mx=max(mx, v[j-1]);
            dp[i]=min(dp[i], dp[j-1]+mx);
        }
        res=(res+p[n-i]*dp[i])%mod;
        //cout<<i<<' '<<dp[i]<<'\n';
    }
    return res;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -