Submission #381660

#	Time	Username	Problem	Language	Result	Execution time	Memory
381660		usachevd0	Growing Vegetables is Fun 4 (JOI21_ho_t1)	C++14	100 / 100	33 ms	8300 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
void debug_out() { cerr << endl; }
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); }
template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
#ifdef DEBUG
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto x : v) stream << x << ' '; return stream; }
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; }

signed main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  vector<ll> a(n);
  for (auto& x : a) {
    cin >> x;
  }
  auto prec = [&](vector<ll>& val, vector<ll>& cost) {
    val.resize(n);
    cost.resize(n);
    val[0] = a[0];
    cost[0] = 0;
    for (int i = 1; i < n; ++i) {
      val[i] = max(a[i], val[i - 1] + 1);
      ll d = val[i] - a[i];
      ll d1 = val[i - 1] - a[i - 1];
      cost[i] = cost[i - 1] + max(0LL, d - d1);
    }
  };
  vector<ll> pval, pcost;
  prec(pval, pcost);
  vector<ll> sval, scost;
  reverse(all(a));
  prec(sval, scost);
  reverse(all(a));
  reverse(all(sval));
  reverse(all(scost));
  debug(pval);
  debug(pcost);
  debug(sval);
  debug(scost);
  ll ans = 1e18;
  for (int i = 0; i < n; ++i) {
    ll cur = max(pcost[i], scost[i]);
    /*if (pval[i] <= sval[i]) {
      ll d = sval[i] - pval[i];
      cur += i * d;
    } else {
    }*/
    chkmin(ans, cur);
  }
  cout << ans << '\n';
    
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:24: warning: statement has no effect [-Wunused-value]
   26 |     #define debug(...) 1337
      |                        ^~~~
Main.cpp:65:3: note: in expansion of macro 'debug'
   65 |   debug(pval);
      |   ^~~~~
Main.cpp:26:24: warning: statement has no effect [-Wunused-value]
   26 |     #define debug(...) 1337
      |                        ^~~~
Main.cpp:66:3: note: in expansion of macro 'debug'
   66 |   debug(pcost);
      |   ^~~~~
Main.cpp:26:24: warning: statement has no effect [-Wunused-value]
   26 |     #define debug(...) 1337
      |                        ^~~~
Main.cpp:67:3: note: in expansion of macro 'debug'
   67 |   debug(sval);
      |   ^~~~~
Main.cpp:26:24: warning: statement has no effect [-Wunused-value]
   26 |     #define debug(...) 1337
      |                        ^~~~
Main.cpp:68:3: note: in expansion of macro 'debug'
   68 |   debug(scost);
      |   ^~~~~

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