제출 #1089329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089329		LePhiPhat	Peru (RMI20_peru)	C++17	0 / 100	0 ms	348 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 minStack {
public:
  stack<pair<T, T>> st;

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

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

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

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

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

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

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

template <class T> class minDeque {
public:
  minStack<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 getMin() {
    assert(stackB.size() || stackF.size());

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

    return min(stackF.getMin(), stackB.getMin());
  }
};

void debugLn(minDeque<int> de) {
  cout << "[ ";
  while (de.stackF.size()) {
    cout << de.stackF.top() << ", ";
    de.stackF.pop();
  }
  vector<int> v;
  while (de.stackB.size()) {
    v.push_back(de.stackB.top());
    de.stackB.pop();
  }

  while (not v.empty()) {
    cout << v.back() << ", ";
    v.pop_back();
  }

  cout << "]\n";
}

const i64 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;

  minDeque<int> dq;
  deque<int> ind_dq, ind;

  ind.push_back(0);
  dq.push_back(dp[0]);
  ind_dq.push_back(0);

  for (int i = 1; i <= N; i++) {
    while (!ind.empty() && a[ind.back()] <= a[i]) {
      ind.pop_back();
    }

    while (!ind_dq.empty() && i - ind_dq.front() > K) {
      ind_dq.pop_front();
      dq.pop_front();
    }

    while (!ind.empty() && i - ind.front() >= K) {
      ind.pop_front();
    }

    // cout << "i = " << i << "\n dq = ";
    // debugLn(dq);
    // debug(ind_dq);
    // debug(ind);

    if (ind.empty()) {
      mini(dp[i], dp[max(i - K, 0)] + a[i]);
    } else {
      mini(dp[i], dp[ind.back()] + a[i]);
      mini(dp[i], dp[max(i - K, 0)] + max(a[i], a[ind.front()]));
    }

    ind.push_back(i);
    ind_dq.push_back(i);
    dq.push_back(dp[i]);
  }

  // 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;
}

#ifdef LOCAL
signed main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  int N = 8, K = 2;
  cin >> N >> K;

  int a[N];

  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }

  cout << solve(N, K, a);
}
#endif

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