QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#486521 | #8554. Bot Friends | BalintR | TL | 1ms | 3668kb | C++20 | 2.1kb | 2024-07-21 20:55:08 | 2024-07-21 20:55:09 |
Judging History
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);
ms(newDp, -INF);
newDp[0][0] = 0;
FR(p, SZ(str)){
memcpy(oldDp, newDp, sizeof(oldDp));
ms(newDp, -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});
}
}
}
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';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 7 6 6 6 7 6 5 8 6 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 5 8 7 8 5 6 5 7 8 8 8 8 7 5 5 7 7 6 8 7 5 8 6 6 8 7 7 6 8 5 7 6 6 5 5 7 7 5 3 8 6 5 7 5 7 6 7 7 8 3 8 8 7 8 7 7 4 8 8 7 5 8 6 7 7 8 7 5 7 8 5 7 6 5 8 8 7 7 8 6 7 8 6 6 8 7 8 7 6 5 5 7 8 6 8 6 7 5 7 4 6 6 7 7 7 ...