제출 #534804

#제출 시각아이디문제언어결과실행 시간메모리
534804Paul_Liao_1457Growing Vegetables is Fun 4 (JOI21_ho_t1)C++14
0 / 100
1 ms204 KiB
// 還要更強 #include<iostream> #include<queue> #include<set> #include<map> #include<iomanip> #include<math.h> #include<cstring> #include<stack> #include<string.h> #include<random> #include<algorithm> #include<vector> #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define INF (ll)(2e18) #define pb push_back #define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; ll b[200005],a[200005]; vector<ll> r,l; signed main(){ AC; bool ok=1; int n; cin>>n; FOR(i,1,n+1) cin>>a[i]; FOR(i,1,n+1){ b[i]=a[i]-a[i-1]; if(b[i]>=0) r.pb(i); else l.pb(i); if(b[i]==0) ok=0; } if(ok&&r[r.size()-1]<l[0]){ cout<<0<<endl; return 0; } reverse(l.begin(),l.end()); ll ans=0; FOR(i,2,n+1){ if(b[i]==0){ ans++; if(r.size()&&l.size()&&r.back()>l[0]){ if(b[r.back()]==0){ r.pop_back(); } b[r.back()]--; } } else if(b[i]<0&&r.size()&&r.back()>i){ l.pop_back(); ans+=(1-b[i]); if(r.size()&&l.size()&&l.back()<r.back()){ b[r.back()]-=(1-b[i]); if(b[r.back()]<0){ r.pop_back(); } } } //cout<<"i="<<i<<" ans="<<ans<<endl; } cout<<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...