QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404318#8554. Bot FriendsxlwangWA 35ms3760kbC++142.0kb2024-05-03 19:37:522024-05-03 19:37:53

Judging History

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

  • [2024-05-03 19:37:53]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:3760kb
  • [2024-05-03 19:37:52]
  • 提交

answer

#include<bits/stdc++.h>
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
using namespace std;
inline int read(){
	int x=0;
	bool f=0;
	char c=getchar();
	while(!isdigit(c)) f|=(c=='-'),c=getchar();
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
//	int t=read();
//	while(t--) work();
//}
const int Maxn=5e3+10,inf=1e7;
int f[Maxn][Maxn][2];
char c[Maxn];
int n;
inline void chkmin(int &x,int y){if(x>y) x=y;}
inline void work(){
    scanf("%s",c+1);n=strlen(c+1);
    fr(i,0,n) fr(j,0,n) f[i][j][0]=f[i][j][1]=inf;
    f[0][0][0]=0;
    fr(i,0,n-1) fr(j,0,n) fr(p,0,1){
        if(f[i][j][p]==inf) continue;
        if(c[i+1]!='>'){
            if(j>0) chkmin(f[i+1][j-1][0],f[i][j][p]);
            else chkmin(f[i+1][0][0],f[i][j][p]+1);
        }
        if(c[i+1]!='<'){
            if(p==0){
                chkmin(f[i+1][j][1],f[i][j][p]+1);
                chkmin(f[i+1][j+1][1],f[i][j][p]+1);
                chkmin(f[i+1][j+2][1],f[i][j][p]+1);
            }
            else chkmin(f[i+1][j+1][1],f[i][j][p]);
        }
    }
    // fr(i,0,n) fr(j,0,n) fr(p,0,1) if(f[i][j][p]!=inf) cout<<i<<' '<<j<<' '<<p<<' '<<f[i][j][p]<<endl;
    writeln(n-min(f[n][0][0],f[n][0][1]));
}
inline void init(){
    int t=read();
    while(t--) work();
}
signed main(){
	// freopen("input.in","r",stdin);
	// freopen("output.out","w",stdout);
    init();
    // printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 35ms
memory: 3756kb

input:

100000
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
>><>><<<<<
>?>?>?<<>>
?><?<<?<><
???><>?>?>
<??>?<<><?
??>><?<>>>
<><><?<>>?
?>>?>???><
?<?><?<<>?
>>><?<??><
><><<>?>?<
>?><>><<<?
>??>?><?<>
?????<><?>
<><<?<<>?<
><?>>?>?>?
?><><<<>>?
?<>?<>?<<<
<><<<<<>>>
?>?>?><<>>
<>?<>><>?<
<<<?<>>...

output:

8
7
8
5
6
8
-9999990
7
6
7
-9999990
6
8
7
8
7
8
7
7
6
6
7
7
-9999990
-9999990
6
-9999990
9
6
-9999990
5
7
-9999990
8
7
6
8
7
8
6
6
7
4
2
7
-9999990
8
7
8
6
6
-9999990
7
8
8
8
8
7
-9999990
-9999990
7
7
6
8
8
6
8
6
7
8
7
7
-9999990
8
5
7
6
-9999990
5
5
7
7
6
-9999990
8
6
6
7
-9999990
7
-9999990
7
7
8
...

result:

wrong answer 7th numbers differ - expected: '6', found: '-9999990'