QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390891 | #8554. Bot Friends | pope | WA | 56ms | 3704kb | C++20 | 2.1kb | 2024-04-16 05:23:34 | 2024-04-16 05:23:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<(b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define trav(a, x) for(auto& a : x)
#define f first
#define s second
#define pb push_back
const char nl = '\n';
#ifdef DBG
void dbg_out() { cerr << nl; }
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cerr << ' ' << H;
dbg_out(T...);
}
#define dbg(...) dbg_out(__VA_ARGS__);
#else
#define dbg(...)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int t; cin >> t;
while (t--) {
string s; cin >> s;
int n = sz(s);
// find the first k < and > to the left of i
int ptrL[n+1][n+2];
int ptrR[n+1][n+2];
rep(i, 0, n+1) rep(j, 0, n+2) ptrL[i][j]=ptrR[i][j]=-1;
rep(i, 1, n+1) {
int cntL = 0, cntR = 0;
ptrL[i][cntL] = ptrR[i][cntR] = i;
for (int j = i; j >= 1; j--) {
if (s[j-1] != '>') {
ptrL[i][++cntL] = j-1;
}
if (s[j-1] != '<') {
ptrR[i][++cntR] = j-1;
}
}
}
int dp[n+1]; dp[0] = 0; // count max number of good robots
rep(i, 1, n+1) {
dp[i] = dp[i-1];
rep(len, 1, i+1) {
int jj = -1, j = -1;
if ((jj=ptrL[i][len]) != -1 && (j=ptrR[jj][len])!= -1) {
dp[i] = max(dp[i], dp[j]+2*len-1);
}
if ((jj=ptrL[i][len+1]) != -1 && (j=ptrR[jj][len])!= -1) {
dp[i] = max(dp[i], dp[j]+2*len);
}
if ((jj=ptrL[i][len]) != -1 && (j=ptrR[jj][len+1])!= -1) {
dp[i] = max(dp[i], dp[j]+2*len);
}
}
}
cout << dp[n] << nl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3704kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 56ms
memory: 3644kb
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 7 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'