oj.uz

Submission #1061763

# Submission time Handle Problem Language Result Execution time Memory
1061763 2024-08-16T12:56:11 Z MilosMilutinovic Peru (RMI20_peru) C++14
18 / 100
 600 ms 9848 KB 
#include "peru.h"
#include <bits/stdc++.h>

using namespace std;

const int md = 1e9 + 7;

int add(int x, int y) {
  return x + y < md ? x + y : x + y - md;
}

int mul(int x, int y) {
  return x * 1LL * y % md;
}

int solve(int n, int k, int* v) {
  const long long inf = (long long) 1e18;
  vector<long long> dp(n, inf);
  for (int i = 0; i < n; i++) {
    int mx = 0;
    for (int j = i; j >= 0; j--) {
      if (i - j + 1 > k) {
        break;
      }
      mx = max(mx, v[j]);
      dp[i] = min(dp[i], (j == 0 ? 0LL : dp[j - 1]) + mx);
    }
  }
  int res = 0;
  int pw = 1;
  for (int i = n - 1; i >= 0; i--) {
    dp[i] %= md;
    res = add(res, mul(pw, dp[i]));
    pw = mul(pw, 23);
  }
  return res;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 0 ms 352 KB Output is correct
15 Correct 429 ms 5728 KB Output is correct
16 Correct 384 ms 9556 KB Output is correct
17 Correct 202 ms 9848 KB Output is correct
18 Correct 247 ms 9552 KB Output is correct
19 Correct 303 ms 9752 KB Output is correct
20 Correct 579 ms 9560 KB Output is correct
21 Correct 397 ms 9556 KB Output is correct
22 Execution timed out 785 ms 9752 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 5728 KB Output is correct
2 Correct 384 ms 9556 KB Output is correct
3 Correct 202 ms 9848 KB Output is correct
4 Correct 247 ms 9552 KB Output is correct
5 Correct 303 ms 9752 KB Output is correct
6 Correct 579 ms 9560 KB Output is correct
7 Correct 397 ms 9556 KB Output is correct
8 Execution timed out 785 ms 9752 KB Time limit exceeded
9 Halted 0 ms 0 KB -