제출 #983950

#제출 시각아이디문제언어결과실행 시간메모리
983950vjudge1Growing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms520 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h>//i am gay #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define He_he_boy ios_base::sync_with_stdio(0) , cin.tie(0) ,cout.tie(0) #define ld long double///i like negr a #define pb push_back #define pf push_front #define fi first #define se second #define ll long long #define ull unsigned long long #define all(a) a.begin(), a.end() #define open freopen ("herding.in", "r", stdin); #define close freopen("herding.out", "w", stdout); using namespace std; using namespace __gnu_pbds; const ll mod = 1e9 + 7; ll mod_2 = 998244353; typedef tree<long long, null_type, less_equal<long long> /* � ���������� less_equal<ll> */, rb_tree_tag, tree_order_statistics_node_update>pbds; ll nok(ll n1, ll n2) { return n1 * n2 / __gcd(n1, n2); } ll qpow_mod(ll a, ll b, ll md) { ll res = 1; a = a % md; while (b > 0) { if (b & 1) res = (res * a) % md; a = (a * a) % md; b >>= 1; } return res; } ll pros(ll n) { if (n == 1) { return 1; } for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { return 0; } } return 1; } /// -------------------------------------------------------- void Ali(){ ll n; cin >> n; ll a[n + 19] = {}, b[n + 19] = {}, c[n + 19] = {}; for(ll i = 1;i <= n;i ++){ cin >> a[i]; b[i] = a[i]; c[i] = a[i]; } ll dp[n + 19] = {}, dp2[n + 19] = {}, ans[n + 19] = {}; for(ll i = 2;i <= n;i ++){ ans[i] = ans[i - 1]; if(a[i] <= a[i - 1]){ dp[i] = a[i - 1] - a[i] + 1; a[i] = a[i - 1] + 1; if(dp[i - 1] > 0){ ans[i] += max(0ll, dp[i] - dp[i - 1]); } else{ ans[i] += dp[i]; } } } ll ans2[n + 19] = {}; for(ll i = n - 1;i >= 1;i --){ ans2[i] = ans2[i + 1]; if(b[i + 1] >= b[i]){ dp2[i] = b[i + 1] - b[i] + 1; b[i] = b[i + 1] + 1; if(dp2[i + 1] > 0){ ans2[i] += max(0ll, dp2[i] - dp2[i + 1]); } else{ ans2[i] += dp2[i]; } } } ll mn = 1e18; for(ll i = 1;i <= n;i ++){ ll s = max(a[i - 1], b[i + 1]); if(c[i] <= s){ mn = min(mn, s - c[i] + 1 + max(ans[i - 1], ans2[i + 1])); } else{ mn = min(mn, max(ans[i - 1], ans2[i + 1])); } } cout << mn << '\n'; } /// */* ------------------------------- */* int main() { He_he_boy; ll nigga = 1; // cin >> nigga; while(nigga--){ Ali(); } /* Are you sure bro ? */ } /// */* ------------------------------- */*
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...