QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722337#8554. Bot FriendsKellyWLJWA 71ms5816kbC++172.3kb2024-11-07 18:39:232024-11-07 18:39:23

Judging History

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

  • [2024-11-07 18:39:23]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:5816kb
  • [2024-11-07 18:39:23]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

const int N = 5010;
template<typename T>
void print(T x) {
    if(x < 0)  putchar('-'), x = -x;
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int n, a[N], f[N][N][2], g[N][N][2], ans;
char s[N];
void chkmax(int &a, int b)  {a < b && (a = b);}
void mian() {
    cin >> (s + 1), n = strlen(s + 1), ans = 0;
    for(int i = 0; i <= n + 1; ++i)
        for(int j = 0; j <= n + 1; ++j) f[i][j][0] = f[i][j][1] = g[i][j][0] = g[i][j][1] = -N;
    f[n + 1][0][1] = 0;
    for(int i = n; i > 0; --i) {
        for(int j = 0; j <= n - i; ++j) {
            if(s[i] != '>') chkmax(f[i][j + 1][1], max(f[i + 1][j][0], f[i + 1][j][1])); // i to left 
            if(s[i] != '<') { // i to right
                chkmax(f[i][j][0], f[i + 1][j][1]); 
                chkmax(f[i][j][0], f[i + 1][j][0]);
                if(j)   chkmax(f[i][j - 1][0], f[i + 1][j][0] + 2), chkmax(f[i][j - 1][0], f[i + 1][j][1] + 1);
            }
            // cerr << f[i + 1][j][0] << " " << f[i + 1][j][1] << " ";
        }   
        // cerr << "\n";
    }
    g[0][0][1] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < i; ++j) {
            if(s[i] != '<') chkmax(g[i][j + 1][1], max(g[i - 1][j][0], g[i - 1][j][1])); // i to right 
            if(s[i] != '>') { // i to left
                chkmax(g[i][j][0], g[i - 1][j][1]); 
                chkmax(g[i][j][0], g[i - 1][j][0]);
                if(j)   chkmax(g[i][j - 1][0], g[i - 1][j][0] + 2), chkmax(g[i][j - 1][0], g[i + 1][j][1] + 1);
            }
            // cerr << g[i][j][0] << " " << g[i][j][1] << " ";
        }   
        // cerr << "\n";
    }
    for(int i = 0; i <= n; ++i) {
        int tmp = 0, res = 0;
        for(int j = 0; j < i; ++j) chkmax(tmp, max(g[i][j][0], g[i][j][1]));
        for(int j = 0; j <= n - i; ++j) chkmax(res, max(f[i + 1][j][0], f[i + 1][j][1]));
        chkmax(ans, tmp + res);
    }   
    print(ans), putchar('\n');
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T = 1;  cin >> T;
    while(T--)  mian();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5724kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 71ms
memory: 5816kb

input:

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

output:

8
7
8
5
6
8
6
7
6
7
6
6
8
7
8
6
8
7
7
6
6
6
7
2
6
6
3
9
6
6
5
7
5
8
6
5
8
7
8
6
6
7
4
2
7
6
8
7
8
6
6
5
7
8
8
8
8
7
5
6
7
7
6
8
8
6
8
6
7
8
7
6
6
8
5
7
6
6
5
5
7
7
6
4
8
6
6
7
5
7
6
6
6
8
3
8
8
7
8
7
6
4
8
8
7
5
8
6
7
8
8
7
5
6
8
5
7
6
5
8
8
7
7
8
6
7
8
6
6
8
7
8
7
6
6
5
7
8
6
8
6
7
5
7
4
6
6
7
7
7
...

result:

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