QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#487362 | #8554. Bot Friends | BalintR | WA | 0ms | 3684kb | C++20 | 1.1kb | 2024-07-22 20:37:26 | 2024-07-22 20:37:27 |
Judging History
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'