Submission #306040

#	Time	Username	Problem	Language	Result	Execution time	Memory
306040		TadijaSebez	Monochrome Points (JOI20_monochrome)	C++11	100 / 100	29 ms	4464 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=400050;
char s[N];
ll ans[N];
int n;
void Add(int l,int r,int f){
	if(l>r)return;
	if(l<0)l+=n,r+=n;
	if(r>=n)Add(l,n-1,f),Add(0,r-n,f);
	else ans[l]+=f,ans[r+1]-=f;
}
int main(){
	scanf("%i",&n);
	scanf("%s",s+1);
	vector<int> b,w;
	for(int i=1;i<=2*n;i++){
		if(s[i]=='B')b.pb(i);
		else w.pb(i);
	}
	//for(int i:b)printf("%i ",i);printf("\n");
	//for(int i:w)printf("%i ",i);printf("\n");
	auto Get=[&](int i,int j){
		int x=abs(i-j)-1;
		return min(x,2*n-x-2);
	};
	for(int z=0,o=0,p=0,q=0;z<n;z++){
		int i=b[z];
		while(o<n&&w[o]<i)o++;
		p=max(p,o);
		while(p<n&&Get(w[p],i)==w[p]-i-1)p++;
		while(q<o&&Get(w[q],i)!=i-w[q]-1)q++;
		//printf("%i %i %i %i\n",i,q,o,p);
		Add(o-z,p-1-z,-i-1);
		Add(p-z,n-1-z,2*n+i-1);
		Add(0-z,q-1-z,2*n-i-1);
		Add(q-z,o-1-z,i-1);
	}
	swap(b,w);
	for(int z=0,o=0,p=0,q=0;z<n;z++){
		int i=b[z];
		while(o<n&&w[o]<i)o++;
		p=max(p,o);
		while(p<n&&Get(w[p],i)==w[p]-i-1)p++;
		while(q<o&&Get(w[q],i)!=i-w[q]-1)q++;
		//Add(o+z,p-1+z,-i);
		Add(z-(p-1),z-o,-i);
		//Add(p+z,n-1+z,i);
		Add(z-(n-1),z-p,i);
		//Add(0+z,q-1+z,-i);
		Add(z-(q-1),z-0,-i);
		//Add(q+z,o-1+z,i);
		Add(z-(o-1),z-q,i);
	}
	ll sol=0,sum=0;
	for(int i=0;i<n;i++){
		sum+=ans[i];
		sol=max(sol,sum);
	}
	printf("%lld\n",sol/2);
	/*
	int best=0;
	for(int i=0;i<n;i++){
		if(Get(b[0],w[i])>Get(b[0],w[best]))best=i;
	}
	ll ans=0;
	for(int t=best-1000;t<=best+1000;t++){
		ll now=0;
		for(int z=0;z<n;z++){
			int i=b[z],j=w[(z+t+n)%n];
			now+=Get(i,j);
		}
		ans=max(ans,now);
	}
	printf("%lld\n",ans/2);*/
	return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
monochrome.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~

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