oj.uz

Submission #857620

# Submission time Handle Problem Language Result Execution time Memory
857620 2023-10-06T14:21:02 Z boris_mihov Peru (RMI20_peru) C++17
18 / 100
 600 ms 17240 KB 
#include "peru.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 2500000 + 10;
const int MOD = 1e9 + 7;
const llong INF = 1e18;
const int INTINF = 1e9;

int n, k;
int a[MAXN];
llong dp[MAXN];
int solve(int N, int K, int* v)
{
    n = N; k = K;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = v[i - 1];
    }

    dp[0] = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        int max = 0;
        dp[i] = INF;
        for (int j = 1 ; j <= std::min(i, k) ; ++j)
        {
            max = std::max(max, a[i - j + 1]);
            dp[i] = std::min(dp[i], dp[i - j] + max);
        }
    }

    int ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        ans = (1LL * ans * 23 + dp[i]) % MOD;
    }

    return ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6584 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6584 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 521 ms 17088 KB Output is correct
16 Correct 423 ms 17240 KB Output is correct
17 Correct 253 ms 17084 KB Output is correct
18 Correct 268 ms 17236 KB Output is correct
19 Correct 357 ms 17088 KB Output is correct
20 Execution timed out 684 ms 17092 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 17088 KB Output is correct
2 Correct 423 ms 17240 KB Output is correct
3 Correct 253 ms 17084 KB Output is correct
4 Correct 268 ms 17236 KB Output is correct
5 Correct 357 ms 17088 KB Output is correct
6 Execution timed out 684 ms 17092 KB Time limit exceeded
7 Halted 0 ms 0 KB -