Submission #602233

#	Time	Username	Problem	Language	Result	Execution time	Memory
602233		Mher	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	40 / 100	1092 ms	2604 KiB

Main

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200003;

int n;
int a[N];
int dl[N], dr[N];
long long fa = 1e18;

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];    
  }
  for (int k = 1; k <= n; k++)
  {
    for (int i = 1; i <= n; i++)
    {
      dl[i] = a[i] - a[i - 1];
      dr[i] = a[i] - a[i + 1];
    }
    int l = 1, r = n;
    long long ans = 0;
    while (l != r)
    {
      //cout << l << ' ' << r << ' ' << ans << endl;
      if (r == k)
      {
        int d = max(-dl[l] + 1, 0);
        ans += d;
        dl[l] += d;
        dr[r] += d;
        l++;
      }
      else if (l == k)
      {
        int d = max(-dr[r] + 1, 0);
        ans += d;
        dl[l] += d;
        dr[r] += d;
        r--;
      }
      else if (dl[l] > dr[r])
      {
        int d = max(-dl[l] + 1, 0);
        ans += d;
        dl[l] += d;
        dr[r] += d;
        l++;
      }
      else
      {
        int d = max(-dr[r] + 1, 0);
        ans += d;
        dl[l] += d;
        dr[r] += d;
        r--;
      }
    }
    ans += max(max(-dl[l] + 1, 0), max(-dr[r] + 1, 0));
    //cout << ans << endl;
    fa = min(ans, fa);  
  }
  cout << fa;
  return 0;
}

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