Submission #371608

#	Time	Username	Problem	Language	Result	Execution time	Memory
371608		S920105123	Monochrome Points (JOI20_monochrome)	C++14	25 / 100	2065 ms	512 KiB

monochrome

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
const int MAXN = 200005;
//const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 1e9 + 7;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, arr[MAXN];
vector<int> W, B;

LL check2(int d) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		int mat1 = (i + d) % n;
		for (int j = 0; j < i; j++) {
			int mat2 = (j + d) % n;
			int l1 = W[i], r1 = B[mat1];
			int l2 = W[j], r2 = B[mat2];
			if (l1 > r1) swap(l1, r1);
			int in1 = (l1 <= l2 && l2 <= r1), in2 = (l1 <= r2 && r2 <= r1);
			res += (in1 != in2);
		}
	}
	return res;
}

void solve() {
	cin >> n;
	for (int i = 0; i < 2 * n; i++) {
		char ch;
		cin >> ch;
		arr[i] = (ch == 'B');
		if (arr[i]) B.push_back(i);
		else W.push_back(i);
	}
	
	LL ans = 0;
//	for (int d = 0; d < n; d++) {
//		ans = max(ans, check(d));
//	}
	for (int d = 0; d < n; d++) {
		ans = max(ans, check2(d));
	}
	cout << ans << '\n';
}

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

	int tc = 1;
//	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}

	return 0;
} 

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