CUBE-T006: C-Value

#include <bits/stdc++.h>
using namespace std;

enum index {
    EVEN = 0, ODD = 1
};

typedef long long lli;

const int N = 1e6;
const int Nd2 = 5e5;

lli qsum[2][Nd2 + 10], dp[2];

int main(){

    int nNumber;
    scanf("%d", &nNumber);
    int lastEven = nNumber >> 1;
    int lastOdd = (nNumber + 1) >> 1;
    for(int i = 1; i <= nNumber; ++i){
        int x;
        scanf("%d", &x);
        int idx = (i + 1) >> 1;
        if(i % 2 == 0){
            qsum[EVEN][idx] += qsum[EVEN][idx - 1] + x;
        } else {
            qsum[ODD][idx] += qsum[ODD][idx - 1] + x;
        }
    }

    lli mn = 1e18;
    for(int i = 1; i <= nNumber; ++i){
        int curr = i % 2;
        int prev = curr ^ 1;
        int idx = (i + 1) >> 1;
        if(i % 2 == 0){
            int x = qsum[EVEN][idx] - qsum[EVEN][idx - 1];
            dp[curr] = min(dp[prev] - x, qsum[EVEN][idx - 1] - qsum[ODD][idx] - x);
        } else {
            int x = qsum[ODD][idx] - qsum[ODD][idx - 1];
            dp[curr] = min(dp[prev] + x, qsum[EVEN][idx - 1] - qsum[ODD][idx - 1] + x);
        }
        mn = min(mn, dp[curr] + qsum[EVEN][lastEven] - qsum[EVEN][idx] - qsum[ODD][lastOdd] + qsum[ODD][idx]);
    }
    cout << min(mn, qsum[EVEN][lastEven] - qsum[ODD][lastOdd]);

    return 0;
}