QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728019 | #8554. Bot Friends | fryan | WA | 69ms | 3700kb | C++20 | 1.6kb | 2024-11-09 14:23:32 | 2024-11-09 14:23:45 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
const int mxn = 500;
int n;
string s;
int dp[mxn][mxn][2];
//dp[x][x][0] = prev >
//dp[x][x][1] = prev <
int go(string &s) {
n = sz(s);
for (int i=0; i<=n; i++) {
for (int j=0; j<=n; j++) {
dp[i][j][0] = -mxn*mxn;
dp[i][j][1] = -mxn*mxn;
}
}
dp[0][0][0] = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
// if (dp[i][j][0] != -1) {
if (s[i] != '<') {
dp[i+1][j+1][0] = max(dp[i+1][j+1][0], dp[i][j][0]);
dp[i+1][j+1][0] = max(dp[i+1][j+1][0], dp[i][j][1]);
}
if (s[i] != '>') {
if (j) {
dp[i+1][j-1][1] = max(dp[i+1][j-1][1], dp[i][j][0]+1);
dp[i+1][j-1][1] = max(dp[i+1][j-1][1], dp[i][j][1]+2);
} else {
dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0]);
dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][1]);
}
if (j >= 2) {
dp[i+1][j-2][1] = max(dp[i+1][j-2][1], dp[i][j][0]+2);
dp[i+1][j-2][1] = max(dp[i+1][j-2][1], dp[i][j][1]+3);
}
}
// }
}
}
int mx = 0;
for (int i=0; i<=n; i++) {
mx = max(mx, dp[n][i][0]);
mx = max(mx, dp[n][i][1]);
if (i) {
mx = max(mx, dp[n][i][1]+1);
}
}
return mx;
}
void solve() {
cin>>s;
int res = go(s);
reverse(all(s));
for (int i=0; i<sz(s); i++) {
if (s[i]=='>') s[i]='<';
else if (s[i]=='<') s[i]='>';
}
res = max(go(s),res);
cout<<res<<"\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin>>t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 69ms
memory: 3700kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 8 7 7 6 7 6 5 8 7 8 6 8 8 7 6 6 6 7 2 6 6 4 9 6 6 5 7 5 9 7 6 8 7 8 7 7 8 4 2 7 5 8 7 9 6 7 5 7 8 8 9 8 7 5 6 7 7 6 8 8 7 7 6 7 8 7 7 5 8 6 7 7 6 5 6 7 8 7 4 8 6 6 7 5 7 7 7 7 8 3 8 9 7 8 7 7 5 8 8 7 5 8 7 7 8 8 7 5 7 9 6 7 6 6 9 8 7 7 8 7 7 8 7 6 8 7 9 7 6 8 5 7 8 7 8 6 7 6 7 5 7 7 7 7 8 ...
result:
wrong answer 7th numbers differ - expected: '6', found: '7'