제출 #486159

#제출 시각아이디문제언어결과실행 시간메모리
486159bigDuckGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++14
100 / 100
24 ms6976 KiB
#include<bits/stdc++.h> using namespace std; #define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define mp make_pair #define pb push_back #define ft first #define sc second #define ll long long #define pii pair<int, int> #define count_bits __builtin_popcount #define int ll inline char get_ (){ const int oo=1000005; static char buf[oo], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, oo, stdin), p1 == p2) ? EOF : *p1 ++; } int read_ () { char c = get_(); int sum = 0; while(!(c >= '0' && c <= '9')) c = get_(); while(c >= '0' && c <= '9') sum = sum * 10 + (c - '0'), c = get_(); return sum; } int n, a[200010]; int st[200010], dr[200010]; int32_t main(){ INIT cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; } for(int i=2; i<=n; i++){ st[i]=st[i-1]; if(a[i]<(a[i-1]+1) ){ st[i]+=a[i-1]+1-a[i]; } } for(int i=(n-1); i>=1; i--){ dr[i]=dr[i+1]; if(a[i]<(a[i+1]+1) ){ dr[i]+=a[i+1]+1-a[i]; } } int res=1e18; for(int i=1; i<=n; i++){ res=min(max(st[i-1], dr[i+1] )+max(0ll, max(a[i-1]+1, a[i+1]+1)-a[i] ) , res ); } cout<<res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...