QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532773 | #8554. Bot Friends | chenxinyang2006 | WA | 98ms | 10160kb | C++20 | 2.4kb | 2024-08-25 11:32:28 | 2024-08-25 11:32:28 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;
template <class T>
void chkmax(T &x,T y){
if(x < y) x = y;
}
template <class T>
void chkmin(T &x,T y){
if(x > y) x = y;
}
inline int popcnt(int x){
return __builtin_popcount(x);
}
inline int ctz(int x){
return __builtin_ctz(x);
}
/*ll power(ll p,int k = mod - 2){
ll ans = 1;
while(k){
if(k % 2 == 1) ans = ans * p % mod;
p = p * p % mod;
k /= 2;
}
return ans;
}*/
int T,n;
char s[5005];
int dp[2][5005][5005],opt[2][5005][5005];
void solve(){
scanf("%s",s + 1);
n = strlen(s + 1);
rep(i,0,n + 1){
fill(dp[0][i],dp[0][i] + n + 1,-inf);
fill(dp[1][i],dp[1][i] + n + 1,-inf);
dp[0][i][i] = dp[1][i][i] = 0;
}
rep(len,2,n){
rep(i,1,n){
int j = i + len - 1,pl,pr;
if(j > n) break;
pl = i;pr = j - 1;
if(len > 2){
chkmax(pl,opt[0][i][j - 1]);
chkmin(pr,opt[0][i + 1][j]);
}
rep(k,pl,pr){
if(dp[0][i][k] + dp[0][k + 1][j] > dp[0][i][j]){
opt[0][i][j] = k;
dp[0][i][j] = dp[0][i][k] + dp[0][k + 1][j];
}
}
pl = i;pr = j - 1;
if(len > 2){
chkmax(pl,opt[1][i][j - 1]);
chkmin(pr,opt[1][i + 1][j]);
}
rep(k,pl,pr){
if(dp[1][i][k] + dp[1][k + 1][j] > dp[1][i][j]){
opt[1][i][j] = k;
dp[1][i][j] = dp[1][i][k] + dp[1][k + 1][j];
}
}
if(s[j] != '>') chkmax(dp[0][i][j],dp[1][i][j - 1] + 1);
if(s[i] != '<') chkmax(dp[1][i][j],dp[0][i + 1][j] + 1);
// assert(opt[0][i][j] >= opt[0][i][j - 1] && opt[1][i][j] >= opt[1][i][j - 1]);
// if(len > 2) assert(opt[0][i][j] <= opt[0][i + 1][j] && opt[1][i][j] <= opt[1][i + 1][j]);
// printf("[%d,%d] [0]%d [1]%d\n",i,j,dp[0][i][j],dp[1][i][j]);
}
}
int answer = max(dp[0][1][n],dp[1][1][n]);
rep(i,1,n - 1) chkmax(answer,dp[0][1][i] + dp[1][i + 1][n]);
printf("%d\n",answer);
}
int main(){
// freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10160kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 98ms
memory: 10096kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 8 7 7 6 7 7 6 8 7 8 7 8 7 7 6 7 7 7 5 7 6 5 9 7 7 5 7 7 9 7 6 8 7 8 8 6 7 6 4 7 7 8 7 9 6 6 6 7 8 8 8 8 7 6 7 7 7 7 8 8 6 8 6 7 8 7 7 7 8 6 7 7 7 5 6 7 8 6 6 8 7 7 7 6 7 7 7 7 8 6 8 9 7 8 7 7 6 8 8 7 6 8 7 7 8 8 7 5 7 8 6 7 7 7 8 8 7 7 8 8 8 8 7 7 8 7 8 7 6 8 6 7 8 7 8 7 7 6 7 7 7 7 7 7 8 ...
result:
wrong answer 7th numbers differ - expected: '6', found: '7'