Submission #294155

#	Time	Username	Problem	Language	Result	Execution time	Memory
294155		pit4h	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	2053 ms	2836 KiB

monochrome

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#ifndef LOCAL
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
int n;
void inc(int& x) {
	x =  (x+1)%(2*n);	
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	string s; cin>>s;
	ll best = 0;
	for(int i=1; i<2*n; ++i) {
		if(s[i]==s[0]) continue;
		ll ans = 0;
		vector<bool> intersect(2*n, 1);
		int cnt = 1;
		vector<int> matched(2*n, -1);
		matched[0] = matched[i] = 0;
		int b = 1, w = i;			
		inc(w);	
		int iter = 1;
		while(iter<n) {
			while(s[b]!=s[0]) {
				if(matched[b] != -1) {
					intersect[matched[b]] = !intersect[matched[b]];
					if(intersect[matched[b]]) {
						cnt++;
					}
					else {
						cnt--;
					}
				}
				inc(b);
			}

			while(s[w]==s[0]) {
				if(matched[w] != -1) {
					intersect[w] = !intersect[w];
					if(intersect[w]) {
						cnt++;
					}
					else {
						cnt--;
					}
				}
				inc(w);
			}
			matched[b] = matched[w] = b;
			ans += cnt;
			cnt++;
			iter++;
			inc(b); inc(w);
		}
		best = max(best, ans);
	}
	cout<<best;
}

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