QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640573#9454. String of CCPChaze#TL 0ms3724kbC++231.5kb2024-10-14 14:24:592024-10-14 14:24:59

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 14:24:59]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3724kb
  • [2024-10-14 14:24:59]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define irep(i,l,r) for(int i = l; i <= r; ++ i)
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(0);

const int N = 200000 + 7;

int a[N];

void solve(){
	int n;
	string s;
	cin >> n >> s;
	s.push_back('$');
	s.push_back('$');
	s.push_back('$');
	s.push_back('$');
	s.push_back('$');
	
	s = "$" + s;
	int sum = 0, d = 0;
	auto check = [&](int i){
		if(i == 0)return false;
		if(i + 3 > n)return false;
		if(s[i] == 'C' and s[i + 1] == 'C' and s[i + 2] == 'P' and s[i + 3] == 'C')
			return true;
		return false;
	};
	a[0] = 0;
	irep(i, 1, n){
		if(check(i))
			a[i] = 1;
		else a[i] = 0;
	}
	sum = accumulate(a + 1, a + n + 1, 0);
	if(s[1] == 'C' and s[2] == 'P' and s[3] == 'C')d = 1;
	irep(p, 1, n){
		int d1 = 0;
		irep(i, min(1, p - 2), p)d1 -= a[i];
		irep(i, min(1, p - 2), p + 1){
			string temp = "";
			irep(j, i, p)temp.push_back(s[j]);
			temp.push_back('C');
			for(int j = p + 1; temp.length() < 4; ++ j)
				temp.push_back(s[j]);
			if(temp == "CCPC")
				++ d1;
		}
		d = max(d, d1);
		d1 = 0;
		irep(i, min(1, p - 2), p)d1 -= a[i];
		irep(i, min(1, p - 2), p + 1){
			string temp = "";
			irep(j, i, p)temp.push_back(s[j]);
			temp.push_back('P');
			for(int j = p + 1; temp.length() < 4; ++ j)
				temp.push_back(s[j]);
			if(temp == "CCPC")
				++ d1;
		}
		d = max(d, d1);

	}
	cout << sum + d << '\n';
}

int main(){
	IOS
	int T;
	cin >> T;
	while(T --){
		solve();
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3724kb

input:

3
3
CCC
5
CCCCP
4
CPCP

output:

1
1
1

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

20003
5
PCCPC
10
CPPPPCPCPC
4
CPPC
11
CCPPCPPPCCP
17
PPPPCPCCCCCPCCCCC
10
PPCCPCPPCP
9
CPCCCCPPC
11
PCPPPPCCPPP
15
CPCPPPPCCPCPCCC
11
PCCPPCCPCPP
9
PCPCCPPCP
10
CCPCPPPCPP
14
CCCCPPPCPCPCPP
2
CC
12
CCPCPPPPPCPP
6
CPPPPP
12
PCCPCCCCCPCC
16
CPCCPCCPPCCCCPPC
7
CPPPCPC
16
PPPPPCCPCPCPCPPC
13
PPPCPCCCCPP...

output:

1
1
0
1
2
1
1
1
2
2
1
1
1
0
1
0
2
2
1
2
1
1
2
0
1
1
3
1
1
3
1
2
2
1
0
0
0
3
1
0
0
1
1
1
0
1
1
0
1
2
0
1
0
1
0
3
1
1
0
2
1
2
2
2
0
2
2
0
0
2
1
1
3
3
1
2
1
2
0
1
1
0
1
2
2
1
1
1
1
3
1
1
3
1
2
2
0
1
0
3
0
1
1
1
2
0
2
1
1
2
2
0
3
1
1
1
1
1
1
1
0
1
1
0
2
0
3
1
1
0
0
1
0
3
0
1
1
1
1
1
2
1
1
0
0
1
2
0
1
2
...

result: