Submission #623144

#	Time	Username	Problem	Language	Result	Execution time	Memory
623144		S2speed	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	1747 ms	10892 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;

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

ll cal(ll k){
	if(c[k] != -1) return c[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;
	return c[k] = cur;
}

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

	memset(c , -1 , sizeof(c));
	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 sq = 500;
	ll res = 0;
	for(ll i = 0 ; i < n ; i += sq){
		c[i] = cal(i);
		res = max(res , c[i]);
	}
	bool f = false;
	for(ll i = sq ; i < n ; i += sq){
		f |= (c[i - sq] < c[i]);
		if(c[i - sq] >= c[i] && f){
			for(ll j = max(0ll , i - (sq << 1)) ; j <= i ; j++){
				res = max(res , cal(j));
			}
			cout<<res<<'\n';
			return 0;
		}
	}
	for(ll i = max(0ll , n - (sq << 1)) ; i < n ; i++){
		res = max(res , cal(i));
	}
	for(ll i = 0 ; i < sq ; i++){
		res = max(res , cal(i));
	}
	cout<<res<<'\n';
	return 0;
}

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