제출 #341975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341975		wwdd	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	18 ms	5768 KiB

monochrome

//this code is gross
#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];
	}
	sort(pr.begin(),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