Submission #1158671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158671		alexander707070	Monochrome Points (JOI20_monochrome)	C++20	25 / 100	2095 ms	328 KiB

monochrome

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,br[MAXN];
char c[MAXN];
vector<int> B,W;
vector< pair<int,int> > pairs;

long long ans;

bool cross(pair<int,int> a,pair<int,int> b){
	if(a.first<b.first and b.second<a.second)return false;
	if(b.first<a.first and a.second<b.second)return false;
	if(a.second<b.first or b.second<a.first)return false;

	return true;
}

long long solve(){
	
	long long res=0;

	for(auto a:pairs){
		for(auto b:pairs){
			if(a==b)continue;
			if(cross(a,b))res++;
		}
	}

	res/=2;

	return res;
}

int main(){

	cin>>n;
	for(int i=1;i<=2*n;i++){
		cin>>c[i];
		if(c[i]=='B')B.push_back(i);
		else W.push_back(i);
	}

	for(int pref=0;pref<=n;pref++){
		bool ok=true;
		pairs.clear();

		for(int i=0;i<pref;i++){
			if(B[i] > W[n-pref+i]){
				ok=false; break;
			}

			pairs.push_back({B[i],W[n-pref+i]});
		}

		for(int i=pref;i<n;i++){
			if(B[i] < W[i-pref]){
				ok=false; break;
			}

			pairs.push_back({W[i-pref],B[i]});
		}

		if(!ok)continue;

		ans=max(ans,solve());
	}

	cout<<ans<<"\n";

	return 0;
}

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