oj.uz

Submission #925886

# Submission time Handle Problem Language Result Execution time Memory
925886 2024-02-12T10:23:12 Z boris_mihov Monochrome Points (JOI20_monochrome) C++17
0 / 100
 2 ms 4700 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 2e9;

int n;
int w[MAXN];
int b[MAXN];
char s[MAXN];
std::vector <std::pair <int,int>> v;

int solveFor(int k)
{
    v.clear();
    for (int i = 1 ; i <= n ; ++i)
    {
        v.push_back({std::min(w[i], b[(i + k - 1) % n + 1]), std::max(w[i], b[(i + k - 1) % n + 1])});
    }

    int res = 0;
    std::sort(v.begin(), v.end());
    for (int i = 0 ; i < n ; ++i)
    {
        for (int j = i + 1 ; j < n ; ++j)
        {
            res += (v[j].first < v[i].second && v[i].second < v[j].second);
        }
    }

    return res;
}

void solve()
{
    int cntW = 1;
    int cntB = 1;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        if (s[i] == 'W') w[cntW++] = i;
        else b[cntB++] = i;
    }

    int max = 0;
    for (int i = 0 ; i < n ; ++i)
    {
        max = std::max(max, solveFor(i));
        if (i >= 1 && i < n - 1)
        {
            assert(solveFor(i - 1) - solveFor(i) >= solveFor(i) - solveFor(i + 1));
        }
    }

    std::cout << max << '\n';
}

void input()
{
    std::cin >> n;
    std::cin >> s + 1;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

monochrome.cpp: In function 'void input()':
monochrome.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     std::cin >> s + 1;
      |                 ~~^~~

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 2 ms 4700 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 2 ms 4700 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 2 ms 4700 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Runtime error 2 ms 4700 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -