Submission #623129

#	Time	Username	Problem	Language	Result	Execution time	Memory
623129		S2speed	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	2055 ms	7892 KiB

monochrome

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

typedef long long ll;
typedef pair<ll , ll> pll;

const ll maxn = 4e5 + 17;

string s;
vector<ll> a , b;
ll ps[maxn];

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

	ll n;
	cin>>n>>s;
    for(ll i = 0 ; i < (n << 1) ; i++){
		if(s[i] == 'B'){
			a.push_back(i);
		} else {
			b.push_back(i);
		}
	}
	ps[0] = (s[0] == 'B');
	for(ll i = 1 ; i < (n << 1) ; i++){
		ps[i] = ps[i - 1] + (s[i] == 'B');
	}
	ll res = 0;
	for(ll k = 0 ; k < n ; k++){
		ll cur = 0;
		for(ll t = 0 ; t < n ; t++){
			ll i = a[t] , j = b[(t + k) % n];
			if(i < j){
				ll h1 = ps[j] - ps[i] , h0 = j - i - 1 - h1 , b0 = n - 1 - h0 , h = max(0ll , h1 - b0);
				cur += j - i - 1 - (h << 1);
			} else {
				ll d = (n << 1) - (i - j + 1) , h1 = n - ps[i] + ps[j] , h0 = d - h1 , b0 = n - 1 - h0 , h = max(0ll , h1 - b0);
				cur += d - (h << 1);
			}
		}
		cur >>= 1;
		res = max(res , cur);
	}
	cout<<res<<'\n';
	return 0;
}

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