Submission #62987634

---

Source Code Expand

// LUOGU_RID: 204166611
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
vector<ll> a, b;

void f() {
  ll n; string s; cin >> n >> s;
  a.assign(n, 0);
  b.assign(n, 0);
  for(ll i=0, curr=0; i<n; i++){
    if(i) a[i]=a[i-1];
    if(s[i]=='0') a[i]+=curr;
    else curr++;
  }
  for(ll i=n-1, curr=0; i>=0; i--){
    if(i!=n-1) b[i]=b[i+1];
    if(s[i]=='0') b[i]+=curr;
    else curr++;
  }
  ll ans=n*n*n;
  for(ll i=0; i<n-1; i++){
    ans=min(ans, a[i]+b[i+1]);
  }
  cout << ans << endl;
}

int main() {
  int tc=1; 
  // cin >> tc;
  while (tc--){
    // cout << '#' << tc << endl;
    f();
    cout << endl;
  }
}

Submission Info

Judge Result