oj.uz

Submission #1106410

# Submission time Handle Problem Language Result Execution time Memory
1106410 2024-10-30T09:28:52 Z LucaLucaM Peru (RMI20_peru) C++17
0 / 100
 1 ms 336 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>
#warning That's not the baby, that's my baby

#define debug(x) #x << " = " << x << '\n'
using ll = long long;

const ll INF = 1e18;
const int mod = 1e9 + 7;

int toHash(std::vector<ll> x) {
  int ret = 0;
  for (int i = 0; i < (int) x.size(); i++) {
    x[i] %= mod;
    ret = ((ll) ret * 23 + x[i]) % mod;
  }  
  return ret;
}

struct Info {
  int index, maxi;
  ll cost;
};

int solve(int n, int k, int *A) {
  std::vector<ll> dp(n + 1, INF);
  std::vector<int> a(n + 1, 0);
  for (int i = 0; i < n; i++) {
    a[i + 1] = A[i];
  }

  dp[0] = 0;
  std::deque<Info> deq;
  deq.push_back({0, 0, 0});
  for (int i = 1; i <= n; i++) {
    int ptr = (int) deq.size() - 1;
    while (ptr >= 0 && deq[ptr].maxi < a[i]) {
      deq[ptr].cost += a[i] - deq[ptr].maxi;
      deq[ptr].maxi = a[i];
      ptr--;
    }
    dp[i] = deq.front().cost;
    while (!deq.empty() && deq.front().index <= i - k + 1) {
      deq.pop_front();
    }
    Info me;
    me.index = i;
    me.cost = dp[i - 1] + a[i];
    me.maxi = a[i];
    while (!deq.empty() && me.cost < deq.back().cost) {
      deq.pop_back();
    }
    deq.push_back(me);
  }

  dp.erase(dp.begin());
  // std::cout << "\n\nDP: ";
  // for (int i = 0; i < n; i++) {
  //   std::cout << dp[i] << ' ';
  // }
  return toHash(dp);
}

#ifdef LOCAL
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n, k;
  std::cin >> n >> k;

  int *a = new int[n];
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
  }

  std::cout << solve(n, k, a);

  return 0;
}
#endif

Compilation message

peru.cpp:6:2: warning: #warning That's not the baby, that's my baby [-Wcpp]
    6 | #warning That's not the baby, that's my baby
      |  ^~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -