oj.uz

Submission #708340

# Submission time Handle Problem Language Result Execution time Memory
708340 2023-03-11T15:25:30 Z Cyanmond Monochrome Points (JOI20_monochrome) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using i64 = long long;

int main() {
    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;
    std::vector<int> blackPos, whitePos;
    for (int i = 0; i < 2 * N; ++i) {
        if (S[i] == 'B') blackPos.push_back(i);
        if (S[i] == 'W') whitePos.push_back(i);
    }
    for (int i = 0; i < 3 * N; ++i) blackPos.push_back(blackPos[i] + 2 * N);
    for (int i = 0; i < 3 * N; ++i) whitePos.push_back(whitePos[i] + 2 * N);

    auto calc = [&](const int w) {
        // blackPos[i] - whitePos[i + w]
        std::vector<std::pair<int, int>> ps;
        for (int i = 0; i < N; ++i) {
            int a = blackPos[i], b = whitePos[i + w];
            while (b >= 2 * N) b -= 2 * N;
            ps.push_back({a, b});
        }
        i64 cnt = 0;
        for (int i = 0; i < N; ++i) {
            int b = i + 1;
            while (b != i and blackPos[b] < whitePos[i + w] and whitePos[b + w] < blackPos[i] + 2 * N) {
                ++b;
            }
            cnt += b - i - 1;
        }
        return cnt;
    };

    i64 answer = 0;
    for (int i = 0; i < N; ++i) answer = std::max(answer, calc(i));
    std::cout << answer << std::endl;
    return 0;

    int l = -1, r = N;
    while (r - l > 2) {
        int x1 = (2 * l + r) / 3, x2 = (l + 2 * r) / 3;
        const auto v1 = calc(x1), v2 = calc(x2);
        if (v1 > v2) r = x2;
        else l = x1;
    }
    std::cout << calc((l + r) / 2) << std::endl;
}

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -