Submission #1061770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061770		MilosMilutinovic	Peru (RMI20_peru)	C++14	100 / 100	378 ms	74292 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) {
  vector<int> ft(n);
  deque<int> dq;
  for (int i = 0; i < n; i++) {
    while (!dq.empty() && v[i] >= v[dq.back()]) {
      dq.pop_back();
    }
    while (!dq.empty() && i - dq.front() + 1 > k) {
      dq.pop_front();
    }
    dq.push_back(i);
    ft[i] = v[dq.front()];
  }
  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});
    st.emplace((border == 0 ? 0LL : dp[border - 1]) + v[i], border);
    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);
    dp[i] = min(dp[i], (j == 0 ? 0LL : dp[j - 1]) + ft[i]);
  }
  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 / 18
• Subtask 2: 31 / 31
• Subtask 3: 51 / 51