제출 #650258

#제출 시각아이디문제언어결과실행 시간메모리
650258BackNoobGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
34 ms8572 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 5e5 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } int n; ll a[mxN]; ll b[mxN]; int lef[mxN]; int rig[mxN]; ll pre[mxN]; ll suf[mxN]; void solve() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1]; for(int i = 2; i <= n; i++) { b[i] = a[i] + pre[i - 1]; pre[i] = pre[i - 1] + max(0LL, b[i - 1] + 1 - b[i]); b[i] = max(b[i], b[i - 1] + 1); } b[n] = a[n]; for(int i = n - 1; i >= 1; i--) { b[i] = a[i] + suf[i + 1]; suf[i] = suf[i + 1] + max(0LL, b[i + 1] + 1 - b[i]); b[i] = max(b[i], b[i + 1] + 1); } ll res = infll; for(int i = 1; i <= n; i++) minimize(res, max(pre[i], suf[i])); cout << res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen(TASK".inp" , "r" , stdin); //freopen(TASK".out" , "w" , stdout); int tc = 1; //cin >> tc; while(tc--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...