QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#486822#8554. Bot FriendsBalintRWA 33ms3648kbC++202.4kb2024-07-22 04:38:512024-07-22 04:38:51

Judging History

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

  • [2024-07-22 04:38:51]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:3648kb
  • [2024-07-22 04:38:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

const int MN = 5005;
int n;
string str;
int oldDp[2][MN], newDp[2][MN];

int solve(){
    cin >> str;
    n = SZ(str);
    FR(s, 2) FR(i, n+1) newDp[s][i] = -INF;
    newDp[0][0] = 0;

    FR(p, SZ(str)){
        FR(s, 2) FR(i, n+1) oldDp[s][i] = newDp[s][i], newDp[s][i] = -INF;
        if(str[p] != '<') FR(i, p+1){
            int v = max(oldDp[0][i], oldDp[1][i]);
            newDp[0][i+1] = max(newDp[0][i+1], v);
            newDp[1][i] = max(newDp[1][i], v);
        }
        if(str[p] != '>'){
            newDp[0][0] = max({newDp[0][0], oldDp[0][0], oldDp[1][0]+1});
            FOR(i, 1, p+1){
                newDp[1][i-1] = max({newDp[1][i-1], oldDp[1][i]+2, oldDp[0][i]+1});
                newDp[0][i] = max(newDp[0][i], oldDp[0][i]);
                newDp[1][i] = max(newDp[1][i], oldDp[1][i]);
            }
        }

        // dbgArr(newDp[0], p+2);
        // dbgArr(newDp[1], p+2);
    }

    int res = 0;
    FR(s, 2) FR(i, n+1) res = max(res, newDp[s][i]);
    return res;
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) cout << solve() << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 33ms
memory: 3544kb

input:

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

output:

8
7
8
5
6
8
6
7
6
7
6
6
8
7
8
7
8
7
7
6
6
7
7
2
6
6
3
9
6
5
5
7
5
8
7
6
8
7
7
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
7
6
8
6
7
8
7
7
6
8
5
7
6
6
5
5
7
7
6
4
8
6
6
7
5
7
6
7
7
8
3
8
8
7
8
7
7
4
8
8
7
5
8
7
7
8
8
7
5
7
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 30th numbers differ - expected: '6', found: '5'