Submission #296204

#	Time	Username	Problem	Language	Result	Execution time	Memory
296204		maximath_1	Monochrome Points (JOI20_monochrome)	C++11	100 / 100	17 ms	3348 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const ll mod = 1e9 + 7;
const int N = 200005;

int n, v[N * 2], pref[N];
string s;

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	
	cin >> n >> s;
	for(int i = 0; i < 2 * n; i ++)
		v[i] = (s[i] == 'W' ? 1 : -1);

	for(int i = 0; i < n; i ++){
		if(i == 0) pref[i] = v[i] * (v[i] == v[n + i]);
		else pref[i] = pref[i - 1] + v[i] * (v[i] == v[n + i]);
	}
	sort(pref, pref + n);
 
 	ll ans = n * 1ll * (n - 1) / 2;
 	for(int i = 0; i < n; i ++)
 		ans -= abs(pref[n / 2] - pref[i]);
 	cout << ans << endl;

	return 0;
}

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