oj.uz

Submission #474502

# Submission time Handle Problem Language Result Execution time Memory
474502 2021-09-18T14:31:31 Z Alexandruabcde Peru (RMI20_peru) C++14
18 / 100
 600 ms 5212 KB 
#include "peru.h"
#include <iostream>

using namespace std;

constexpr int NMAX = 2500005;
constexpr int MOD = 1e9 + 7;
typedef long long LL;

LL dp[NMAX];
int ans = 0;

int solve(int n, int k, int* v){
    for (int i = 0; i < n; ++ i ) {
        int Max_Effort = v[i];
        dp[i] = 100000000000000000;
        for (int j = i; j > max(0, i-k+1); -- j ) {
            Max_Effort = max(Max_Effort, v[j]);
            dp[i] = min(dp[i], dp[j-1] + 1LL * Max_Effort);
        }

        Max_Effort = max(Max_Effort, v[max(0, i-k+1)]);

        if (i < k) dp[i] = min(dp[i], 1LL * Max_Effort);
        else dp[i] = min(dp[i], dp[i-k] + 1LL * Max_Effort);
    }

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

    return ans;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 583 ms 5024 KB Output is correct
16 Correct 471 ms 5020 KB Output is correct
17 Correct 265 ms 5108 KB Output is correct
18 Correct 302 ms 5020 KB Output is correct
19 Correct 410 ms 5212 KB Output is correct
20 Execution timed out 806 ms 5092 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 583 ms 5024 KB Output is correct
2 Correct 471 ms 5020 KB Output is correct
3 Correct 265 ms 5108 KB Output is correct
4 Correct 302 ms 5020 KB Output is correct
5 Correct 410 ms 5212 KB Output is correct
6 Execution timed out 806 ms 5092 KB Time limit exceeded
7 Halted 0 ms 0 KB -