Submission #1061765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061765		MilosMilutinovic	Peru (RMI20_peru)	C++14	0 / 100	1 ms	348 KiB

peru

#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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51