제출 #1264459

#제출 시각아이디문제언어결과실행 시간메모리
1264459Mauricio_CruzGrowing Vegetables is Fun 4 (JOI21_ho_t1)C++20
0 / 100
0 ms328 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define f first #define s second #define ve vector #define pb push_back #define vi vector<int> int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n;cin>>n; vi a(n); for(int i=0;i<n;i++)cin>>a[i]; vi x(n+1,0),y(n+1,0),x1(n+1),y1(n+1); for(int i=1;i<n;i++){ int v=a[i-1]+x[i-1]+1; v-=a[i]; x[i]=max(0LL,v); } for(int i=n-2;i>=0;i--){ int v=a[i+1]+y[i+1]+1; y[i]=max(0LL,v-a[i]); } x1[0]=x[0]; y1[n-1]=y[n-1]; for(int i=1;i<n;i++){ if(x[i-1]<x[i])x1[i]=x1[i-1]+(x[i]-x[i-1]); else x1[i]=x1[i-1]; } for(int i=n-2;i>=0;i--){ if(y[i+1]<y[i])y1[i]=y1[i+1]+(y[i]-y[i+1]); else y1[i]=y1[i+1]; } int res=min(y1[0],x1[n-1]); for(int i=1;i<n-1;i++){ int v=x[i-1],w=y[i+1]; int val=min(v,w); int r=x1[i-1]+y1[i+1]-val; int num=a[i]+val; r+=max(0LL,max(a[i-1]+1,a[i+1]+1)-num); res=min(res,r); } cout<<res; /* 4 5 3 0 0 3 1 2 4 1 */ return 0; } /* 9 5 10 9 9 8 11 10 7 12 11 10 9 11 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...