oj.uz

Submission #314764

# Submission time Handle Problem Language Result Execution time Memory
314764 2020-10-21T06:37:15 Z kshitij_sodani Election (BOI18_election) C++14
0 / 100
 22 ms 384 KB 
#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;
		/*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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -