QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#487362#8554. Bot FriendsBalintRWA 0ms3684kbC++201.1kb2024-07-22 20:37:262024-07-22 20:37:27

Judging History

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

  • [2024-07-22 20:37:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3684kb
  • [2024-07-22 20:37:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize "Ofast"
#pragma GCC target "avx2"

#define FR(i, n) for(int i = 0; i < (n); i++)

const int MN = 5016;
int n, t;
char str[MN];
short dp[2][2][MN];

int main(){
	scanf("%d ", &t);
    bool curS = 0;
	while(t--){
		scanf("%s", str);
		n = strlen(str);
        FR(a, 2) FR(b, 2) FR(i, n+3) dp[a][b][i] = MN;
		dp[curS][0][0] = 0;

		FR(p, n){
            dp[!curS][1][0] = MN;
			if(str[p] != '<') FR(i, p+1) dp[!curS][1][i+1] = min(dp[curS][0][i], dp[curS][1][i]);
            else FR(i, p+1) dp[!curS][1][i] = MN;

			if(str[p] != '>'){
				FR(i, p+1){
                    short v1 = min<short>(dp[curS][0][i+1], dp[curS][1][i]+1);
                    short v2 = min<short>(dp[curS][1][i+1], dp[curS][1][i+2])+1;
                    dp[!curS][0][i] = min(v1, v2);
                }
                dp[!curS][0][0] = min<short>(dp[!curS][0][0], dp[curS][0][0]+1);
			}
            else FR(i, p+1) dp[!curS][1][i] = MN;

            curS ^= 1;
		}

		int res = n;
		FR(s, 2) FR(i, n+1) res = min(res, dp[curS][s][i]+i);
		printf("%d\n", n-res);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3684kb

input:

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

output:

2
2
3
4
5
8
8
7
8
7

result:

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