Submission #623042

#	Time	Username	Problem	Language	Result	Execution time	Memory
623042		S2speed	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2075 ms	356 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 = 2e5 + 17;

string s;
vector<ll> a , b;
vector<pll> u;

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);
		}
	}
	ll res = 0;
	for(ll k = 0 ; k < n ; k++){
		u.clear();
		for(ll i = 0 ; i < n ; i++){
			u.push_back({a[i] , b[(i + k) % n]});
			if(u.back().first > u.back().second){
				swap(u.back().first , u.back().second);
			}
		}
		ll cur = 0;
		for(ll i = 0 ; i < n ; i++){
			for(ll j = i + 1 ; j < n ; j++){
				bool c = (u[i].first > u[j].first) , d = (u[i].second > u[j].second);
				if(c ^ d) continue;
				if(c){
					cur += (u[i].first < u[j].second);
				} else {
					cur += (u[j].first < u[i].second);
				}
			}
		}
		res = max(res , cur);
	}
	cout<<res<<'\n';
	return 0;
}

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