提出 #66345656

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(a) a.begin(), a.end()
#define NUM1 998'244'353ll
#define NUM2 1'000'000'007ll
#define MOD NUM1
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define sq(a_) ((a_) * (a_))
const ll INF = LLONG_MAX/7;
const ll MAX = 2'50'100ll;


void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> p0(n + 1), p1(n + 1), d(n + 1);
    for(int i = 1; i <= n; i++){
        p0[i] = p0[i - 1];
        p1[i] = p1[i - 1];
        if(s[i - 1] == '0') ++p0[i];
        else ++p1[i];
        d[i] = p0[i] - p1[i];
    }
    // for(auto&x : d) cerr << x << ' ';
    // cerr << '\n';
    int c1 = p1[n];
    int maxd = 0, mind = n;
    for(int i = 1; i <= n; i++){
        maxd = max(maxd, d[i]);
        mind = min(mind, d[i] - maxd);
    }
    cout << c1 + mind << '\n';
}

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // fill(prods, prods + 600, mi(1));
    // fact[0] = 1;
    // for(ll i = 1; i < MAX; i++) fact[i] = i * fact[i - 1];
    // ifact[MAX - 1] = inv(fact[MAX - 1]);
    // for(ll i = MAX - 2; i >= 0; i--) ifact[i] = (i + 1) * ifact[i + 1];
    ll t = 1;
    cin >> t;
    while(t--)
        solve();
    return 0;
}

提出情報

ジャッジ結果