Submission #643987

#	Time	Username	Problem	Language	Result	Execution time	Memory
643987		tvladm2009	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	91 ms	6960 KiB

Main

#include <bits/stdc++.h>

using ll = long long;

const int MAX_N = 200000;

ll a[MAX_N + 1], l[MAX_N + 1], r[MAX_N + 1];

int main() {
  int n;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    l[i] = l[i - 1] + std::max(0LL, a[i - 1] - a[i] + 1);
  }
  for (int i = n; i >= 1; i--) {
    r[i] = r[i + 1] + std::max(0LL, a[i + 1] - a[i] + 1);
  }
  ll answer = (1LL << 60);
  for (int i = 1; i <= n; i++) {
    answer = std::min(answer, std::max(l[i], r[i]));
  }
  std::cout << answer;
  return 0;
}

• Subtask 1: 40 / 40
• Subtask 2: 60 / 60