QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640573 | #9454. String of CCPC | haze# | TL | 0ms | 3724kb | C++23 | 1.5kb | 2024-10-14 14:24:59 | 2024-10-14 14:24:59 |
Judging History
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 ...