Submission #4212545

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
struct UnionFind {
    vector<int> par; // uf(x,y)->y
    UnionFind() {}
    UnionFind(int NV) { init(NV); }
    void init(int NV) { par.clear(); rep(i, 0, NV) par.push_back(i); }
    void reset() { rep(i, 0, par.size()) par[i] = i; }
    int operator[](int x) { return par[x] == x ? x : par[x] = operator[](par[x]); }
    void operator()(int x, int y) { x = operator[](x); y = operator[](y); if (x != y) par[x] = y; }
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/







int L; ll A[201010];
//---------------------------------------------------------------------------------------------------
ll B[201010];
void init() {
    B[0] = A[0];
    rep(i, 1, L) B[i] = B[i - 1] + A[i];
}
ll get(int l, int r) {
    if (!(l <= r)) return 0;
    ll res = B[r];
    if (l) res -= B[l - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
ll ans = 0;
ll dp[201010][3], dp2[201010][3];
void f() {
    init();

    rep(i, 0, L + 1) rep(e, 0, 3) dp[i][e] = infl;
    dp[0][0] = 0;
    rep(i, 0, L) {
        // dp[i][0] -> dp[i+1][0], dp[i+1][1], dp[i+1][2]
        dp[i + 1][0] = dp[i][0] + A[i];

        if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][0] + 1);
        else chmin(dp[i + 1][1], dp[i][0]);
        
        if(A[i] == 0) chmin(dp[i + 1][2], dp[i][0] + 2);
        else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][0]);
        else chmin(dp[i + 1][2], dp[i][0] + 1);

        // dp[i][1] -> dp[i+1][1]
        if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][1] + 1);
        else chmin(dp[i + 1][1], dp[i][1]);

        // dp[i][2] -> dp[i + 1][2], dp[i + 1][1]
        if (A[i] % 2 == 0) chmin(dp[i + 1][1], dp[i][2] + 1);
        else chmin(dp[i + 1][1], dp[i][2]);

        if (A[i] == 0) chmin(dp[i + 1][2], dp[i][2] + 2);
        else if (A[i] % 2 == 0) chmin(dp[i + 1][2], dp[i][2]);
        else chmin(dp[i + 1][2], dp[i][2] + 1);
    }
    rep(i, 1, L + 1) rep(e, 0, 3) chmin(ans, dp[i][e] + get(i, L - 1));

    //rep(i, 0, L + 1) rep(e, 0, 3) printf("dp[%d][%d] = %lld\n", i, e, dp[i][e]);
}
//---------------------------------------------------------------------------------------------------

ll solve() {
    init();
    ans = get(0, L - 1);

    f();

    reverse(A, A + L);
    init();
    swap(dp, dp2);
    
    f();

    rep(i, 1, L) chmin(ans, min(dp[i][1], dp[i][2]) + min(dp2[L - i][1], dp2[L - i][2]));

    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> L;
    rep(i, 0, L) cin >> A[i];
    cout << solve() << endl;
}

Submission Info

Judge Result