QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #632456 | #9454. String of CCPC | ucup-team5052# | AC ✓ | 132ms | 35036kb | C++14 | 1.1kb | 2024-10-12 13:25:40 | 2024-10-12 13:25:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int m=9,INF=1e9;
int f[200010][10][4],ch[4][2];
char s[200010];
void chkmax(int &x,int y){x=max(x,y);}
int main() {
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ch[0][0]=1;
ch[1][0]=2;
ch[2][0]=2;
ch[2][1]=3;
ch[3][0]=1;
int T;
cin>>T;
while(T--)
{
int n,ans=0;
cin>>n>>s+1;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
fill(f[i][j],f[i][j]+4,-INF);
f[0][0][0]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(j<m)
{
for(int k=0;k<4;k++)
{
chkmax(f[i][j+1][ch[k][0]],f[i][j][k]-j+(k==3));
chkmax(f[i][j+1][ch[k][1]],f[i][j][k]-j);
}
}
if(i>=n) break;
if(s[i+1]!='C' && s[i+1]!='P')
{
for(int k=0;k<4;k++) chkmax(f[i+1][j][0],f[i][j][k]);
}
else if(s[i+1]=='C')
{
for(int k=0;k<4;k++) chkmax(f[i+1][j][ch[k][0]],f[i][j][k]+(k==3));
}
else
{
for(int k=0;k<4;k++) chkmax(f[i+1][j][ch[k][1]],f[i][j][k]);
}
}
for(int i=0;i<=m;i++)
for(int j=0;j<4;j++)
chkmax(ans,f[n][i][j]);
cout<<ans<<"\n";
}
return 0;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3 3 CCC 5 CCCCP 4 CPCP
output:
1 1 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 132ms
memory: 35036kb
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 3 2 1 2 1 2 2 0 1 2 3 1 1 3 1 2 2 1 0 0 0 3 1 0 0 1 1 2 0 1 1 0 1 2 0 1 0 1 0 3 1 1 0 2 1 3 2 2 0 2 2 0 0 2 1 1 3 3 1 3 1 2 0 1 1 0 1 2 2 1 1 2 1 3 1 1 3 1 2 2 0 1 0 3 0 1 1 2 2 0 2 1 1 2 2 0 3 1 1 1 1 2 1 2 0 1 1 0 3 0 3 1 1 0 0 1 0 3 0 1 1 1 1 2 2 1 1 0 0 1 2 0 1 2 ...
result:
ok 20003 lines
Extra Test:
score: 0
Extra Test Passed