1860D - Balanced String - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e8 + 69;

int main() {
  string s; cin >> s;
  int n = s.size(), zero = 0, one = 0;
  for (char &c : s) c == '0' ? ++zero : ++one; 
  int bound = zero * one, dim = bound << 1 | 1;
  vector DP(one + 1, vector(dim, INF));
  for (int i = 0; i <= zero; ++i) {
    vector newDP(one + 1, vector(dim, INF));
    for (int j = 0; j <= one; ++j) {
      if (!i and !j) {
        newDP[j][bound] = 0;
        continue;
      }
      int c = s[i + j - 1] - '0';
      for (int k = 0; k <= dim; ++k) {
        if (i and k + one - j <= dim) newDP[j][k] = min(newDP[j][k], DP[j][k + one - j] + c);
        if (j and k - zero + i >= 0) newDP[j][k] = min(newDP[j][k], newDP[j - 1][k - zero + i] + !c);
      }
    }
    DP.swap(newDP);
  }
  cout << DP[one][bound] / 2 << '\n';
  return 0;
}