oj.uz

Submission #493453

# Submission time Handle Problem Language Result Execution time Memory
493453 2021-12-11T12:01:56 Z Jeff12345121 Peru (RMI20_peru) C++14
0 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#include "peru.h"
using namespace std;



const int nmax = 400005;
const int ll inf = LLONG_MAX;
const int P = 1000000007;
ll v[nmax],dp[nmax];
int solve(int n, int k, int* s) {
    for (int i = 1; i <= n; i++)
        v[i] = s[i - 1];
    for (int i = 1; i <= n; i++) dp[i] = inf;
    for (int i = 1; i <= n; i++) {
        ll maxSoFar = -1;
        for (int j = i - 1; j >= 0 && j >= i - k; j--) {
            maxSoFar = max(maxSoFar , v[j + 1]);
            dp[i] = min(dp[i] , dp[j] + maxSoFar);
        }
    }

    ll put23 = 1;
    int sum = 0;
    for (int i = n; i >= 1; i--) {
        sum = (1ll * sum + dp[i] * put23) % P;
        put23 = ( put23 * 23 ) % P;
    }
  //  out << sum << "\n";
    return sum;
}
/*
int main() {
    int s[nmax];
    int n = 8, k = 3;
    vector<int> vec = {3 ,2, 9, 8, 7, 11, 3, 4};
    for (int i = 0; i < n; i++) {
        s[i] = vec[i];
    }
    solve(8 , 3 , s);
}*/

Subtask #1
0 / 18.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 51.0

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