oj.uz

Submission #1089223

# Submission time Handle Problem Language Result Execution time Memory
1089223 2024-09-16T07:42:37 Z LePhiPhat Peru (RMI20_peru) C++17
0 / 100
 0 ms 348 KB 
#include "peru.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "algo/debug.cpp"
#else
#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.top();
  }

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

  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());
  }
};

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

  minDeque<int> minDp, val;

  dp[0] = 0;
  val.push_back(0);
  for (int i = 1; i <= N; i++) {

    if (not val.empty() && i - val.front() >= K) {
      val.pop_front();
    }

    while (not val.empty() && a[val.back()] < a[i]) {
      val.pop_back();
    }

    val.push_back(i);

    if (not val.empty())
      debug(i, val.front());

    if (i <= K) {
      dp[i] = max(dp[i - 1], a[i]);
    } else {
      mini(dp[i], dp[i - 1] + a[i]);
      mini(dp[i], dp[i - K] + a[val.front()]);
    }

    debug(i, dp[i]);
  }

  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, K;
  cin >> N >> K;

  int a[N];

  debug(N, K);

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

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

Compilation message

peru.cpp: In function 'int solve(int, int, int*)':
peru.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
peru.cpp:162:7: note: in expansion of macro 'debug'
  162 |       debug(i, val.front());
      |       ^~~~~
peru.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
peru.cpp:171:5: note: in expansion of macro 'debug'
  171 |     debug(i, dp[i]);
      |     ^~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -