Submission #342369

#	Time	Username	Problem	Language	Result	Execution time	Memory
342369		wwdd	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	8 ms	5896 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	string s;
	cin >> s;
	vl rem;
	for(int i=0;i<n;i++) {
		if(s[i] != s[i+n]) {
			rem.push_back(0);
		} else if(s[i] == 'B') {
			rem.push_back(1);
		} else {
			rem.push_back(-1);
		}
	}
	vl pr;
	ll rs = 0;
	for(int i=0;i<n;i++) {
		pr.push_back(rs);
		rs += rem[i];
	}
	nth_element(pr.begin(),pr.begin()+pr.size()/2,pr.end());
	ll piv = -pr[pr.size()/2];
	ll tot = n*(n-1)/2;
	for(int i=0;i<n;i++) {
		tot -= abs(piv);
		piv += rem[i];
	}
	cout << tot << '\n';
}

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