oj.uz

Submission #1061765

# Submission time Handle Problem Language Result Execution time Memory
1061765 2024-08-16T13:06:31 Z MilosMilutinovic Peru (RMI20_peru) C++14
0 / 100
 1 ms 348 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);
  multiset<pair<long long, int>> st;
  vector<array<int, 3>> stk;
  for (int i = 0; i < n; i++) {
    int border = i;
    while (!stk.empty() && v[i] > stk.back()[0]) {
      border = stk.back()[1];
      st.erase({(border == 0 ? 0LL : dp[border - 1]) + stk.back()[0], border});
      stk.pop_back();
    }
    stk.push_back({v[i], border, i});
    while (!st.empty() && i - st.begin()->second + 1 > k) {
      st.erase(st.begin());
    }
    if (!st.empty()) {
      dp[i] = min(dp[i], st.begin()->first);
    }
    int j = max(0, i - k + 1);
    int mx = 0;
    for (int p = j; p <= i; p++) {
      mx = max(mx, v[p]);
    }
    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
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -