Submission #1089226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089226		LePhiPhat	Peru (RMI20_peru)	C++17	18 / 100	1018 ms	12368 KiB

peru

#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.cpp"
#else
#include "peru.h"
#define debug(...) 42
#define debugArr(...) 42
#endif
using namespace std;

template <class X, class Y> bool mini(X &x, const Y &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
template <class X, class Y> bool maxi(X &x, const Y &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

using i64 = long long;

using vi = vector<int>;
template <class T> class maxStack {
public:
  stack<pair<T, T>> st;

  T getMax() { return st.top().second; }

  T empty() { return st.empty(); }

  int size() { return st.size(); }

  void push(T x) {
    T mn = x;
    if (!empty()) {
      maxi(mn, getMax());
    }
    st.push(make_pair(x, mn));
  }

  void pop() { st.pop(); }

  T top() { return st.top().first; }

  void swap(maxStack<T> &another) { st.swap(another.st); }
};

template <class T> class maxDeque {
public:
  maxStack<T> stackF, stackB, stackTmp;

  void rebalance() {
    bool flag = false;
    if (stackF.empty()) {
      stackF.swap(stackB);
      flag = true;
    }

    int sz = stackF.size() / 2;

    while (sz--) {
      stackTmp.push(stackF.top());
      stackF.pop();
    }

    while (!stackF.empty()) {
      stackB.push(stackF.top());
      stackF.pop();
    }

    while (!stackTmp.empty()) {
      stackF.push(stackTmp.top());
      stackTmp.pop();
    }

    if (flag) {
      stackF.swap(stackB);
    }
  }

  bool empty() { return (stackF.empty() && stackB.empty()); }

  int size() { return (stackB.size() + stackF.size()); }

  void push_back(T x) { stackB.push(x); }

  void push_front(T x) { stackF.push(x); }

  void pop_back() {
    assert(stackB.size() || stackF.size());
    if (stackB.empty())
      rebalance();
    stackB.pop();
  }

  void pop_front() {
    assert(stackB.size() || stackF.size());
    if (stackF.empty())
      rebalance();
    stackF.pop();
  }

  T back() {
    if (stackB.empty())
      rebalance();
    return stackB.back();
  }

  T front() {
    if (stackF.empty())
      rebalance();
    return stackF.back();
  }

  T getMax() {
    assert(stackB.size() || stackF.size());

    if (stackF.empty())
      return stackB.getMax();
    if (stackB.empty())
      return stackF.getMax();

    return max(stackF.getMax(), stackB.getMax());
  }
};

const int MOD = 1'000'000'007;

i64 mul(i64 a, i64 b) { return (a % MOD) * (b % MOD) % MOD; }

int solve(int N, int K, int *S) {
  vector<i64> dp(N + 1, 1e16);
  vector<i64> a(N + 1);
  for (int i = 1; i <= N; i++) {
    a[i] = S[i - 1];
  }

  dp[0] = 0;
  for (int i = 1; i <= N; i++) {
    maxDeque<int> de;
    for (int j = 1; j <= K && i - j + 1 >= 1; j++) {
      de.push_back(a[i - j + 1]);
      mini(dp[i], dp[i - j] + de.getMax());
    }
  }

  // for (int i = 1; i <= N; i++) {
  //   cout << dp[i] << " \n"[i == N];
  // }

  i64 cur = 1, ans = 0;
  for (int i = N; i >= 1; i--) {
    ans = (ans % MOD + mul(cur, dp[i])) % MOD;
    cur = mul(cur, 23);
  }

  return ans;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 31
• Subtask 3: 0 / 51