Submission #314769

#	Time	Username	Problem	Language	Result	Execution time	Memory
314769		kshitij_sodani	Election (BOI18_election)	C++14	0 / 100	534 ms	504 KiB

election

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n' 


int n;
string s;
int vis[2001];
int pre[2001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	cin>>s;
	int q;
	cin>>q;
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		if(s[i-1]=='C'){
			pre[i]-=1;
		}
		else{
			pre[i]+=1;
		}
	//	cout<<pre[i]<<":";
	}
//	cout<<endl;
	while(q--){
		int l,r;
		cin>>l>>r;
		l--;
		r--;
		int co=1;
		int ans2=0;
		for(int i=l;i<=r;i++){
			int cot=max(pre[r+1]-pre[i],0)+max(pre[i+1]-pre[l],0);
			if(pre[r+1]-pre[i]>0 and pre[i+1]-pre[l]>0 and s[i]=='T'){
				cot-=1;
			}
	//		cout<<cot<<":";
			ans2=max(ans2,cot);
		}
		for(int i=l;i<=r;i++){
			for(int j=i+1;j<r;j++){
					int cot=max(pre[r+1]-pre[j],0)+max(pre[i+1]-pre[l],0);
					ans2=max(ans2,cot);
			}
		}
//		cout<<endl;
		cout<<ans2<<endl;
		continue;
		/*for(int i=1;i<=n;i++){
			pre[i]=pre[i-1];
			if(s[i-1]=='C'){
				pre[i]-=1;
			}
			else{
				pre[i]+=1;
			}
		//	cout<<pre[i]<<":";
		}
*/
		for(int i=0;i<n;i++){
			vis[i]=0;
		}
		
		for(int i=l;i<=r;i++){
		//	cout<<pre[i+1]<<":"<<pre[l]<<endl;
			if(pre[i+1]-pre[l]==co){
				vis[i]=1;
				co+=1;
			//	cout<<i<<":";
			//	cout<<pre[i+1]<<":"<<pre[l]<<endl;
			}
		}
		for(int i=1;i<=n;i++){
			pre[i]=pre[i-1];
			if(vis[i]!=1){
				if(s[i-1]=='C'){
					pre[i]-=1;
				}
				else{
					pre[i]+=1;
				}
			}
		//	cout<<pre[i]<<":";
		}
	//	cout<<endl;
		int ans=co-1;
		co=1;
		for(int i=r;i>=l;i--){
			if(vis[i]){
				continue;
			}
			if(pre[r+1]-pre[i]==co){
				vis[i]=1;
				co+=1;
			//	cout<<i<<":";
			}
		}
	//	cout<<endl;
		ans=max(ans,co-1);
		ans=0;
		for(int i=0;i<n;i++){
			ans+=vis[i];
		}
		cout<<ans<<endl;





	}










	return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18