Submission #914639

#	Time	Username	Problem	Language	Result	Execution time	Memory
914639		qin	Monochrome Points (JOI20_monochrome)	C++17	25 / 100	2064 ms	600 KiB

monochrome

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n");
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
void answer(){
		int n; scanf("%d", &n);
		char c = char(getchar_unlocked());
		vector<int> t(n<<1), pos_w(n), pos_b(n);
		int w_cnt = 0, b_cnt = 0;
		for(int i = 0; i < n<<1; ++i){
				c = char(getchar_unlocked()), t[i] = c == 'B' ? 1 : 0;
				if(c == 'W') pos_w[w_cnt++] = i;
				else 		 pos_b[b_cnt++] = i;
		}
		ll result = 0;
		vector<int> dp(n<<1, 0), is_start(n<<1, -1);
		for(int offset = 0; offset < n; ++offset){
				ll res_local = 0;
				for(int i = 0; i < n; ++i) is_start[min(pos_b[i], pos_w[(i+offset)%n])] = max(pos_b[i], pos_w[(i+offset)%n]);
											//~ printf("%d %d\n", min(pos_b[i], pos_w[(i+offset)%n]), max(pos_b[i], pos_w[(i+offset)%n]));
				for(int i = 0; i < n<<1; ++i){
						if(is_start[i] != -1){
								res_local += dp[is_start[i]];
								for(int j = is_start[i]; j < n<<1; ++j) ++dp[j];
						}
						else 	for(int j = i; j < n<<1; ++j) --dp[j];
				}
				result = max(result, res_local);
				//~ printf("%lld\n", res_local);
				fill(all(dp), 0), fill(all(is_start), -1);
		}
		printf("%lld\n", result);
}
int main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'void answer()':
monochrome.cpp:14:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~

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