oj.uz

답안 #473898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
473898 2021-09-16T11:41:40 Z Lain Monochrome Points (JOI20_monochrome) C++17
0 / 100
 1 ms 204 KB 
#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.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -