제출 #1255539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255539		kamrad	Monochrome Points (JOI20_monochrome)	C++20	25 / 100	5 ms	328 KiB

monochrome

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

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, ll>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define rand(l, r)        uniform_ll_distribution<ll64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const ll Mod    = 1e9 + 7; //998244353;
const ll LG     = 64;
const ll SQ     = 500;
const ll Inf    = 2e9 + 10;
const ll maxN   = 2e3 + 10;

ll n;
int oc[maxN];

bool a[maxN];

vector <ll> Widx;
vector <ll> Bidx;

struct FenTree {
	ll bit[maxN];
	
	void add(ll idx) {
		for(; idx < maxN; idx += (idx & (-idx))) {
			bit[idx]++;
		}
	}
	
	ll get(ll idx) {
		ll ret = 0;
		for(; idx > 0; idx -= (idx & (-idx))) {
			ret += bit[idx];
		}
		return ret;
	}

	void cle() {
		for(ll i = 0; i < maxN; i++)
			bit[i] = 0;
	}
} f;

ll CountInv(vector <ll> &val) {
	ll ret = 0;
	for(auto x : val) {
		ret += f.get(x-1);
		f.add(x);
	}
	f.cle();
	return ret;
}

ll calc(ll l, ll r, ll k, bool type) {
	ll remain = k;
	for(ll i = (l+1)%(2*n); i != r%(2*n); i = (i+1)%(2*n)) {
		if(a[i] == type and remain) {
			oc[i] = 1;
			remain--;
		}
	}
	remain = k;
	for(ll i = (r-1+2*n)%(2*n); i != l%(2*n); i = (i-1+2*n)%(2*n)) {
		if(a[i] != type and remain) {
			oc[i] = -1;
			remain--;
		}
	}

	ll ret = 0;
ll open = 0;
	for(ll i = l; i != (r+1)%(2*n); i = (i+1)%(2*n)) {
		if(oc[i] == 0)
			ret += open;
		else if(oc[i] == 1)
			ret += open;
		open += oc[i];
	}

	for(ll i = (r+1)%(2*n), cur = 1; i != l; i = (i+1)%(2*n), cur++) {
		if(a[i])
			Bidx.pb(cur);
		else
			Widx.pb(cur);
	}

	ll ptr1 = 0; //on white
	ll ptr2 = 0; //on black
	vector <ll> val;
	for(ll i = (l+1)%(2*n); i != r; i = (i+1)%(2*n)) {
		if(oc[i] == 0) {
			if(a[i]) {
				val.pb(Widx[ptr1]);
				ptr1++;
			}
			else {
				val.pb(Bidx[ptr2]);
				ptr2++;
			}
		}
	}
	ret += CountInv(val);
	ret += sz(val);

	Bidx.clear();
	Widx.clear();
	for(ll i = 0; i < 2*n; i++)
		oc[i] = 0;
	
	return ret;
}

int main() {
	IOS;
	
	cin >> n;
	for(ll i = 0; i < 2*n; i++) {
		char c;
		cin >> c;
		a[i] = (c=='B');
	}
	
	ll ans = 0;
	ll l = 0;
	for(ll r = 1; r < 2*n; r++) {
		ll W1 = 0;
		ll B1 = 0;
		if(a[l] == a[r])
			continue;

		for(ll i = (l+1)%(2*n); i != r; i = (i+1)%(2*n)) {
			if(a[i])
				B1++;
			else
				W1++;
		}

		if(2*n-2-B1-W1 > B1+W1) {
			if(n-1-B1 < W1 or n-1-W1 < B1)
				continue;
			ll k = n-1-B1-W1;
			maxr(ans, calc(r, l, k, !a[r]));
		}
		else {
			if(W1 < n-1-B1 or B1 < n-1-W1)
				continue;
			ll k = W1-(n-1-B1);
			maxr(ans, calc(l, r, k, !a[l]));
		}
	}
	cout << ans;
}

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