Submission #737131

#	Time	Username	Problem	Language	Result	Execution time	Memory
737131		tch1cherin	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++17	100 / 100	89 ms	6192 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int &v : A) {
    cin >> v;
  }
  vector<long long> pref(N), suff(N);
  for (int i = 0; i < N - 1; i++) {
    pref[i + 1] = pref[i] + max(0, A[i] - A[i + 1] + 1);  
  }
  for (int i = N - 2; i >= 0; i--) {
    suff[i] = suff[i + 1] + max(0, A[i + 1] - A[i] + 1);
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < N; i++) {
    ans = min(ans, max(pref[i], suff[i]));
  }
  cout << ans << "\n";
}

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