oj.uz

Submission #645892

# Submission time Handle Problem Language Result Execution time Memory
645892 2022-09-28T08:53:49 Z Vanilla Peru (RMI20_peru) C++17
18 / 100
 600 ms 7640 KB 
#include <bits/stdc++.h>
#include "peru.h"
using namespace std;
typedef long long int64;
const int maxn = 2e3 + 2;
const int64 mod = 1e9 + 7;
int64 dp [maxn];
int64 pw [maxn];
 
int solve(int n, int k, int* v){
    pw[n-1] = 1;
    for (int i = n - 2; i >= 0; i--){
        pw[i] = (pw[i + 1] * 23) % mod;
    }
    int mx = 0;
    for (int i = 0; i < k; i++){
        mx = max(mx, v[i]);
        dp[i] = mx;
    }
    for (int i = k; i < n; i++){
        int mx = 0;
        dp[i] = 1e18;
        for (int j = i; j >= i - k + 1; j--){
            mx = max(mx, v[j]);
            dp[i] = min(dp[i], dp[j - 1] + mx);
        }
        // dp[i] = dp[i - k] + mx;
    }
    int64 rs = 0;
    for (int i = 0; i < n; i++){
        // cout << dp[i] << " ";
        for (int j = 0; j < n - i - 1; j++){
            dp[i] = dp[i] * 23 % mod;
        }
        rs = (rs + dp[i]) % mod;
        // rs = (rs + dp[i] * pw[i]) % mod;
    }
    // cout << "\n";
    return rs;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 11 ms 364 KB Output is correct
3 Correct 11 ms 388 KB Output is correct
4 Correct 11 ms 332 KB Output is correct
5 Correct 11 ms 388 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 10 ms 328 KB Output is correct
8 Correct 11 ms 388 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 10 ms 388 KB Output is correct
12 Correct 11 ms 340 KB Output is correct
13 Correct 11 ms 340 KB Output is correct
14 Correct 11 ms 392 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 340 KB Output is correct
2 Correct 11 ms 364 KB Output is correct
3 Correct 11 ms 388 KB Output is correct
4 Correct 11 ms 332 KB Output is correct
5 Correct 11 ms 388 KB Output is correct
6 Correct 11 ms 340 KB Output is correct
7 Correct 10 ms 328 KB Output is correct
8 Correct 11 ms 388 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 11 ms 332 KB Output is correct
11 Correct 10 ms 388 KB Output is correct
12 Correct 11 ms 340 KB Output is correct
13 Correct 11 ms 340 KB Output is correct
14 Correct 11 ms 392 KB Output is correct
15 Execution timed out 1047 ms 7640 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 7640 KB Time limit exceeded
2 Halted 0 ms 0 KB -