oj.uz

Submission #101806

# Submission time Handle Problem Language Result Execution time Memory
101806 2019-03-20T10:42:04 Z tushar_2658 Election (BOI18_election) C++14
28 / 100
 3000 ms 2464 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 7e4 + 5;
int arr[maxn], arr1[maxn], arr2[maxn], n;
string s;

int solve(int l, int r){
	int cnt = 0;
	int ret = 0;
	bool vis[maxn];
	memset(vis, 0, sizeof vis);
	for(int i=l; i<=r; i++){
		cnt += arr[i];
		if(cnt < 0){
			ret++;
			cnt++;
			vis[i] = 1;
		}
	}
	int ret1 = 0;
	cnt = 0;
	for(int i=r; i>=l; i--){
		if(!vis[i])cnt += arr[i];
		if(cnt < 0){
			ret++;
			cnt++;
		}
	}
	return max(ret, ret1);
}

int main(){
	//freopen("in.txt", "r", stdin);
	cin>>n;
	cin>>s;
	for(int i=1; i<=n; i++){
		if(s[i-1] == 'C')arr[i] = 1;
		else arr[i] = -1;
	}
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<solve(l, r)<<endl;
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 15 ms 512 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 2953 ms 2464 KB Output is correct
7 Execution timed out 3004 ms 1760 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 14 ms 512 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 2953 ms 2464 KB Output is correct
7 Execution timed out 3004 ms 1760 KB Time limit exceeded
8 Halted 0 ms 0 KB -