Submission #557427

#	Time	Username	Problem	Language	Result	Execution time	Memory
557427		erray	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	33 ms	4632 KiB

Main

// author: erray
#include <bits/stdc++.h>

#ifdef DEBUG
  #include "debug.h"
#else
  #define debug(...) void(37)
#endif

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(N + 1);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  vector<long long> cost(N + 1);
  cost[N] = 0;
  for (int i = N - 1; i >= 0; --i) {
    cost[i] = cost[i + 1] + max(0, A[i + 1] - A[i] + 1);
  }
  debug(cost);

  long long ans = (long long) 1e17;
  long long sum = 0;
  for (int i = 0; i < N; ++i) {
    if (i > 1) {
      sum += max(0, A[i - 2] - A[i - 1] + 1);
    }
    ans = min(ans, max(sum, cost[i + 1]) + max({A[i + 1] - A[i] + 1, (i == 0 ? 0 : A[i - 1]) - A[i] + 1, 0}));
  }
  cout << ans << '\n';
}

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