Submission #968247

#TimeUsernameProblemLanguageResultExecution timeMemory
968247Darren0724Line Town (CCO23_day1problem3)C++17
6 / 25
37 ms14060 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define ll long long #define LCBorz ios_base::sync_with_stdio(false);cin.tie(0); const int N=1000005; const int mod=1e6+3; const ll INF=1e18; int32_t main(){ LCBorz; int n;cin>>n; vector<ll> v(n+2),pre(n+2),suf(n+2); for(int i=1;i<=n;i++){ cin>>v[i]; assert(abs(v[i])==1); } ll cnt=0; vector<int> st; for(int i=1;i<=n;i++){ if(v[i]==1){ if(st.size()&&(st.back()+i)%2==1){ cnt+=(i-st.back()); st.pop_back(); } else{ st.push_back(i); } } if(st.size()==0){ pre[i]=cnt; } else{ pre[i]=INF; } } st.clear(); cnt=0; for(int i=n;i>=1;i--){ if(v[i]==-1){ if(st.size()&&(st.back()+i)%2==1){ cnt+=(st.back()-i); st.pop_back(); } else{ st.push_back(i); } } if(st.size()==0){ suf[i]=cnt; } else{ suf[i]=INF; } } ll ans=INF; for(int i=0;i<=n;i++){ ans=min(ans,pre[i]+suf[i+1]); //cout<<pre[i]<<' '<<suf[i+1]<<endl; } if(ans==INF){ cout<<-1<<endl; } else{ cout<<ans<<endl; } return 0; } /* 20 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 1 -1 1 -1 -1 1 4 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...