Submission #473898

#	Time	Username	Problem	Language	Result	Execution time	Memory
473898		Lain	Monochrome Points (JOI20_monochrome)	C++17	0 / 100	1 ms	204 KiB

monochrome

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

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n;
  cin >> n;
  n *= 2;
  string s;
  cin >> s;
  vector<int> black_cnt(n+1), white_cnt(n+1);;
  for (int i = 0; i < n; i++) {
    black_cnt[i+1] = black_cnt[i] + s[i] == 'B';
    white_cnt[i+1] = white_cnt[i] + s[i] == 'W';
  }
  vector<bool> done(n);
  int tot_b = n/2, tot_w = n/2;
  int64_t ans = 0;
  for (int i =0; i < n; i++){
    if (s[i] == 'W') continue;
    int c_b = 0, c_w = 0;
    int best_white = -1, best_ans = -1;
    // Find the crossing number. Use the max
    for (int j = i+1 ; j != i; j=(j+1)%n) {
      if (done[j]) continue;
      if (s[j]== 'W') {
        int o_b = tot_b - c_b-1;
        int o_w = tot_w - c_w-1;
        int curr_ans = min(o_b,c_w) + min(o_w,c_b);
        if (curr_ans > best_ans) {
          best_white = j;
          best_ans = curr_ans;
        }
      }
      c_b += s[j] == 'B';
      c_w += s[j] == 'W';
    }
    assert(best_white != -1);
    ans += best_ans;
    //cout << i << " " << best_white << " " << best_ans << " " << '\n';
    done[i] = done[best_white] = true;
    tot_b--, tot_w--;
  }
  cout << ans << '\n';
}
// This should be wrong..

• Subtask 1: 0 / 4
• Subtask 2: 0 / 21
• Subtask 3: 0 / 10
• Subtask 4: 0 / 65