Submission #1283984

#TimeUsernameProblemLanguageResultExecution timeMemory
1283984am_aadvikMonochrome Points (JOI20_monochrome)C++20
35 / 100
2096 ms21624 KiB
#include <iostream>
#include<vector>
#include<algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define int long long

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; cin >> n;
	string s; cin >> s;
	vector<int> w, b;
	for (int i = 0; i < (n + n); ++i)
		if (s[i] == 'W')
			w.push_back(i);
		else
			b.push_back(i);
	int mx = 0;
	for (int k = 0; k < n; ++k) {
		int ans = 0;
		vector<pair<int, int>> res, a;
		for (int i = 0; i < n; ++i)
			res.push_back({ w[i], b[(i + k) % n] });
		for(int i = 0; i < n; ++i)
		    a.push_back({min(res[i].second, res[i].first), -1}),
		    a.push_back({max(res[i].second, res[i].first), min(res[i].second, res[i].first)});
	    oset s;
	    sort(a.begin(), a.end());
	    for(auto x: a) {
	        if(x.second == -1) s.insert(x.first);
	        else s.erase(x.second),
	            ans += (s.size() - s.order_of_key(x.second));
	    }
		mx = max(ans, mx);
	}
	cout << mx;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...