제출 #1102421

#제출 시각아이디문제언어결과실행 시간메모리
1102421NotLinuxGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++17
0 / 100
1 ms336 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() const int inf = 1e18 + 7; void solve(){ int n; cin >> n; int arr[n]; for(int i = 0;i<n;i++)cin >> arr[i]; int pre[n]={0} , suf[n]={0}; int preval[n] , sufval[n]; preval[0] = arr[0]; for(int i = 1;i<n;i++){ pre[i] = pre[i-1] + max(0ll , preval[i-1] + 1 - arr[i]); preval[i] = max(arr[i] , preval[i-1] + 1); } sufval[n-1] = arr[n-1]; for(int i = n-2;i>=0;i--){ suf[i] = suf[i+1] + max(0ll , sufval[i+1] + 1 - arr[i]); sufval[i] = max(arr[i] , sufval[i+1] + 1); } int global_ans = inf; for(int i = 0;i<n;i++){ int ans[3]; ans[0] = (i == 0 ? 0ll : pre[i-1]); ans[1] = max(i == 0 ? 0ll : preval[i-1] , i == n-1 ? 0ll : sufval[i+1]) + 1 - arr[i]; ans[2] = (i == n-1 ? 0ll : suf[i+1]); int total = ans[0] + ans[1] + ans[2]; // cout << "total : " << ans[0] << " " << ans[1] << " " << ans[2] << " = " << total << endl; int step = min({ans[0] , ans[1] , ans[2]}); ans[0] -= step , ans[1] -= step , ans[2] -= step , total -= 2 * step; // cout << "step1 : " << step << endl; // cout << "total : " << ans[0] << " " << ans[1] << " " << ans[2] << " = " << total << endl; step = min(ans[0] , ans[1]); ans[0] -= step , ans[1] -= step , total -= step; // cout << "step2 : " << step << endl; // cout << "total : " << ans[0] << " " << ans[1] << " " << ans[2] << " = " << total << endl; step = min(ans[1] , ans[2]); ans[1] -= step , ans[2] -= step , total -= step; // cout << "step3 : " << step << endl; // cout << "total : " << ans[0] << " " << ans[1] << " " << ans[2] << " = " << total << endl; // cout << endl; global_ans = min(global_ans , total); } cout << global_ans << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase = 1;//cin >> testcase; while(testcase--)solve(); cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl; } /* * dont get stuck on one approach , try different ones * if you think the implementation is long & messy , change your approach * think simple , dont overkill */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...