Submission #968177

#TimeUsernameProblemLanguageResultExecution timeMemory
968177LittleOrangeLine Town (CCO23_day1problem3)C++17
0 / 25
1 ms348 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const ll big = 1e18; int main(){ ios::sync_with_stdio(0);cin.tie(0); ll n; cin >> n; vector<ll> a(n); for(ll &i : a) cin >> i; vector<array<ll,3>> dp(n+1,{big,big,big}); dp[0] = {0,0,0}; for(ll i = 0;i<n;i++){ if (a[i] == -1){ dp[i+1][0] = min(dp[i+1][0],dp[i][0]); if(i&&a[i-1]==-1) dp[i+1][2] = min(dp[i+1][2],dp[i-1][2]+1); }else if (a[i] == 1){ dp[i+1][2] = min(dp[i+1][2],dp[i][2]); if(i&&a[i-1]==1) dp[i+1][0] = min(dp[i+1][0],dp[i-1][0]+1); }else{ dp[i+1][1] = min(dp[i+1][1],dp[i][1]); } dp[i+1][1] = min(dp[i+1][1],dp[i+1][0]); dp[i+1][2] = min(dp[i+1][2],dp[i+1][1]); } ll ans = dp[n][2]; cout << (ans>=big?-1:ans) << "\n"; }
#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...