답안 #341459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341459	2020-12-29T18:59:53 Z	ryansee	Monochrome Points (JOI20_monochrome)	C++14	100 / 100	381 ms	410860 KB

monochrome

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (600006) // put 6
ll n, ans, grad[MAXN], ofs, neg, pos, zero, best;
deque<int> vv[MAXN];
deque<int>*v=vv+(MAXN/2);
deque<char> A;
ll nC2(ll n) { return n * (n-1) / 2; }
int main() {
	FAST
	cin>>n;
	A.resize(n*2);
	for(auto&i:A)cin>>i;
	FOR(i,0,n-1) {
		if(i) grad[i] += grad[i-1];
		if(A[i] == 'W') {
			-- grad[i];
		}
		if(A[n+i] == 'B') {
			++ grad[i];
		}
		ans += abs(grad[i]);
		v[grad[i]].eb(i);
		neg += grad[i] < 0, pos += grad[i] > 0, zero += grad[i] == 0;
	}
	assert(grad[n-1] == 0);
	FOR(i,0,n*2-1) {
		best = max(best, nC2(n) - ans);
		A.eb(A[0]), A.pop_front();
		
		ll o=grad[i]+ofs;
		neg -= grad[i] + ofs < 0, pos -= grad[i] + ofs > 0, zero -= grad[i] + ofs == 0;
		v[grad[i]].pop_front();

		grad[i] += ofs;		
		grad[i] *= -1;
		
		ans += grad[i] * pos, ans -= grad[i] * neg, ans += abs(grad[i]) * zero, ofs += grad[i];
		if(grad[i]==1){
			pos += zero, zero = v[-ofs].size(), neg -= zero;
		}else if(grad[i]==-1){
			neg += zero, zero = v[-ofs].size(), pos -= zero;
		}else assert(grad[i]==0);
		
		grad[i+n] = grad[i+n-1] + o;
		v[grad[i+n]].eb(i+n);
		
		ans -= abs(o), ans += abs(grad[i+n]+ofs);
		neg += grad[i+n] + ofs < 0, pos += grad[i+n] + ofs > 0, zero += grad[i+n] + ofs == 0;
		
		// FOR(j,i+1,i+n) cerr<<grad[j]<<' '; cerr<<'\n';
		// cerr<<ofs<<'\n';
	}
	cout<<best<<'\n';
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	356 ms	404268 KB	Output is correct
2	Correct	305 ms	404216 KB	Output is correct
3	Correct	305 ms	404204 KB	Output is correct
4	Correct	305 ms	404460 KB	Output is correct
5	Correct	307 ms	404332 KB	Output is correct
6	Correct	308 ms	404500 KB	Output is correct
7	Correct	314 ms	404288 KB	Output is correct
8	Correct	311 ms	404332 KB	Output is correct
9	Correct	306 ms	404204 KB	Output is correct
10	Correct	347 ms	404204 KB	Output is correct
11	Correct	305 ms	404332 KB	Output is correct
12	Correct	310 ms	404460 KB	Output is correct
13	Correct	307 ms	404204 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	356 ms	404268 KB	Output is correct
2	Correct	305 ms	404216 KB	Output is correct
3	Correct	305 ms	404204 KB	Output is correct
4	Correct	305 ms	404460 KB	Output is correct
5	Correct	307 ms	404332 KB	Output is correct
6	Correct	308 ms	404500 KB	Output is correct
7	Correct	314 ms	404288 KB	Output is correct
8	Correct	311 ms	404332 KB	Output is correct
9	Correct	306 ms	404204 KB	Output is correct
10	Correct	347 ms	404204 KB	Output is correct
11	Correct	305 ms	404332 KB	Output is correct
12	Correct	310 ms	404460 KB	Output is correct
13	Correct	307 ms	404204 KB	Output is correct
14	Correct	309 ms	404308 KB	Output is correct
15	Correct	307 ms	404332 KB	Output is correct
16	Correct	306 ms	404332 KB	Output is correct
17	Correct	303 ms	404332 KB	Output is correct
18	Correct	302 ms	404332 KB	Output is correct
19	Correct	305 ms	404332 KB	Output is correct
20	Correct	323 ms	404204 KB	Output is correct
21	Correct	309 ms	404460 KB	Output is correct
22	Correct	305 ms	404332 KB	Output is correct
23	Correct	307 ms	404204 KB	Output is correct
24	Correct	301 ms	404204 KB	Output is correct
25	Correct	303 ms	404332 KB	Output is correct
26	Correct	306 ms	404380 KB	Output is correct
27	Correct	306 ms	404356 KB	Output is correct
28	Correct	306 ms	404332 KB	Output is correct
29	Correct	307 ms	404204 KB	Output is correct
30	Correct	310 ms	404460 KB	Output is correct
31	Correct	303 ms	404332 KB	Output is correct
32	Correct	304 ms	404332 KB	Output is correct
33	Correct	303 ms	404332 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	356 ms	404268 KB	Output is correct
2	Correct	305 ms	404216 KB	Output is correct
3	Correct	305 ms	404204 KB	Output is correct
4	Correct	305 ms	404460 KB	Output is correct
5	Correct	307 ms	404332 KB	Output is correct
6	Correct	308 ms	404500 KB	Output is correct
7	Correct	314 ms	404288 KB	Output is correct
8	Correct	311 ms	404332 KB	Output is correct
9	Correct	306 ms	404204 KB	Output is correct
10	Correct	347 ms	404204 KB	Output is correct
11	Correct	305 ms	404332 KB	Output is correct
12	Correct	310 ms	404460 KB	Output is correct
13	Correct	307 ms	404204 KB	Output is correct
14	Correct	309 ms	404308 KB	Output is correct
15	Correct	307 ms	404332 KB	Output is correct
16	Correct	306 ms	404332 KB	Output is correct
17	Correct	303 ms	404332 KB	Output is correct
18	Correct	302 ms	404332 KB	Output is correct
19	Correct	305 ms	404332 KB	Output is correct
20	Correct	323 ms	404204 KB	Output is correct
21	Correct	309 ms	404460 KB	Output is correct
22	Correct	305 ms	404332 KB	Output is correct
23	Correct	307 ms	404204 KB	Output is correct
24	Correct	301 ms	404204 KB	Output is correct
25	Correct	303 ms	404332 KB	Output is correct
26	Correct	306 ms	404380 KB	Output is correct
27	Correct	306 ms	404356 KB	Output is correct
28	Correct	306 ms	404332 KB	Output is correct
29	Correct	307 ms	404204 KB	Output is correct
30	Correct	310 ms	404460 KB	Output is correct
31	Correct	303 ms	404332 KB	Output is correct
32	Correct	304 ms	404332 KB	Output is correct
33	Correct	303 ms	404332 KB	Output is correct
34	Correct	314 ms	404352 KB	Output is correct
35	Correct	304 ms	404460 KB	Output is correct
36	Correct	318 ms	404460 KB	Output is correct
37	Correct	321 ms	404460 KB	Output is correct
38	Correct	310 ms	404332 KB	Output is correct
39	Correct	307 ms	404460 KB	Output is correct
40	Correct	320 ms	404332 KB	Output is correct
41	Correct	308 ms	404332 KB	Output is correct
42	Correct	317 ms	404332 KB	Output is correct
43	Correct	306 ms	404332 KB	Output is correct
44	Correct	319 ms	404332 KB	Output is correct
45	Correct	307 ms	404332 KB	Output is correct
46	Correct	307 ms	404332 KB	Output is correct
47	Correct	307 ms	404332 KB	Output is correct
48	Correct	304 ms	404332 KB	Output is correct
49	Correct	306 ms	404588 KB	Output is correct
50	Correct	309 ms	404332 KB	Output is correct
51	Correct	311 ms	404332 KB	Output is correct
52	Correct	310 ms	404460 KB	Output is correct

Subtask #4
65.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	356 ms	404268 KB	Output is correct
2	Correct	305 ms	404216 KB	Output is correct
3	Correct	305 ms	404204 KB	Output is correct
4	Correct	305 ms	404460 KB	Output is correct
5	Correct	307 ms	404332 KB	Output is correct
6	Correct	308 ms	404500 KB	Output is correct
7	Correct	314 ms	404288 KB	Output is correct
8	Correct	311 ms	404332 KB	Output is correct
9	Correct	306 ms	404204 KB	Output is correct
10	Correct	347 ms	404204 KB	Output is correct
11	Correct	305 ms	404332 KB	Output is correct
12	Correct	310 ms	404460 KB	Output is correct
13	Correct	307 ms	404204 KB	Output is correct
14	Correct	309 ms	404308 KB	Output is correct
15	Correct	307 ms	404332 KB	Output is correct
16	Correct	306 ms	404332 KB	Output is correct
17	Correct	303 ms	404332 KB	Output is correct
18	Correct	302 ms	404332 KB	Output is correct
19	Correct	305 ms	404332 KB	Output is correct
20	Correct	323 ms	404204 KB	Output is correct
21	Correct	309 ms	404460 KB	Output is correct
22	Correct	305 ms	404332 KB	Output is correct
23	Correct	307 ms	404204 KB	Output is correct
24	Correct	301 ms	404204 KB	Output is correct
25	Correct	303 ms	404332 KB	Output is correct
26	Correct	306 ms	404380 KB	Output is correct
27	Correct	306 ms	404356 KB	Output is correct
28	Correct	306 ms	404332 KB	Output is correct
29	Correct	307 ms	404204 KB	Output is correct
30	Correct	310 ms	404460 KB	Output is correct
31	Correct	303 ms	404332 KB	Output is correct
32	Correct	304 ms	404332 KB	Output is correct
33	Correct	303 ms	404332 KB	Output is correct
34	Correct	314 ms	404352 KB	Output is correct
35	Correct	304 ms	404460 KB	Output is correct
36	Correct	318 ms	404460 KB	Output is correct
37	Correct	321 ms	404460 KB	Output is correct
38	Correct	310 ms	404332 KB	Output is correct
39	Correct	307 ms	404460 KB	Output is correct
40	Correct	320 ms	404332 KB	Output is correct
41	Correct	308 ms	404332 KB	Output is correct
42	Correct	317 ms	404332 KB	Output is correct
43	Correct	306 ms	404332 KB	Output is correct
44	Correct	319 ms	404332 KB	Output is correct
45	Correct	307 ms	404332 KB	Output is correct
46	Correct	307 ms	404332 KB	Output is correct
47	Correct	307 ms	404332 KB	Output is correct
48	Correct	304 ms	404332 KB	Output is correct
49	Correct	306 ms	404588 KB	Output is correct
50	Correct	309 ms	404332 KB	Output is correct
51	Correct	311 ms	404332 KB	Output is correct
52	Correct	310 ms	404460 KB	Output is correct
53	Correct	345 ms	410732 KB	Output is correct
54	Correct	344 ms	410860 KB	Output is correct
55	Correct	348 ms	410348 KB	Output is correct
56	Correct	342 ms	410392 KB	Output is correct
57	Correct	337 ms	410676 KB	Output is correct
58	Correct	337 ms	409964 KB	Output is correct
59	Correct	342 ms	410732 KB	Output is correct
60	Correct	333 ms	409964 KB	Output is correct
61	Correct	349 ms	410732 KB	Output is correct
62	Correct	338 ms	410348 KB	Output is correct
63	Correct	337 ms	410604 KB	Output is correct
64	Correct	333 ms	409836 KB	Output is correct
65	Correct	333 ms	410092 KB	Output is correct
66	Correct	381 ms	410348 KB	Output is correct
67	Correct	334 ms	410348 KB	Output is correct
68	Correct	337 ms	409964 KB	Output is correct
69	Correct	339 ms	410092 KB	Output is correct
70	Correct	337 ms	409836 KB	Output is correct
71	Correct	336 ms	410604 KB	Output is correct
72	Correct	356 ms	410600 KB	Output is correct
73	Correct	335 ms	410732 KB	Output is correct

답안 #341459

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 21.0 / 21.0

Subtask #3 10.0 / 10.0

Subtask #4 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
21.0 / 21.0

Subtask #3
10.0 / 10.0

Subtask #4
65.0 / 65.0