oj.uz

Submission #493454

# Submission time Handle Problem Language Result Execution time Memory
493454 2021-12-11T12:03:18 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 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 -