Submission #968282

#	Time	Username	Problem	Language	Result	Execution time	Memory
968282		Pring	Line Town (CCO23_day1problem3)	C++17	0 / 25	1 ms	348 KiB

Main

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 2005, INF = 1e9;
int n, a[MXN];
vector<int> v;
int pre[MXN], suf[MXN];

int calc() {
    // for (auto &i : v) cout << i << ' ';
    // cout << endl;
    vector<int> st;
    pre[0] = 0;
    int sum = 0;
    FOR(i, 0, v.size()) {
        int &now = pre[i + 1];
        if (st.empty()) st.push_back(v[i]);
        else if ((st.back() + v[i]) & 1) st.push_back(v[i]);
        else {
            sum += v[i] - st.back() / 2;
            st.pop_back();
        }
        now = (st.empty() ? sum : INF);
    }
    for (auto &i : v) i = n - i;
    reverse(v.begin(), v.end());
    st.clear();
    suf[0] = 0;
    sum = 0;
    FOR(i, 0, v.size()) {
        int &now = suf[i + 1];
        if (st.empty()) st.push_back(v[i]);
        else if ((st.back() + v[i]) & 1) st.push_back(v[i]);
        else {
            sum += (v[i] - st.back()) / 2;
            st.pop_back();
        }
        now = (st.empty() ? sum : INF);
    }
    // FOR(i, 0, v.size() + 1) cout << pre[i] << ' ';
    // cout << endl;
    // FOR(i, 0, v.size() + 1) cout << suf[i] << ' ';
    // cout << endl;
    int ans = INF;
    FOR(i, 0, v.size()) ans = min(ans, pre[i] + suf[v.size() - i - 1]);
    return ans;
}

void miku() {
    cin >> n;
    FOR(i, 0, n) {
        cin >> a[i];
    }
    if (a[0] == 1) v.push_back(0);
    FOR(i, 1, n) if (a[i] != a[i - 1]) v.push_back(i);
    if (a[n - 1] == -1) v.push_back(n);
    int x = calc();
    cout << (x >= INF ? -1 : x) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3