제출 #424967

#제출 시각아이디문제언어결과실행 시간메모리
424967MDario건물 4 (JOI20_building4)C++11
0 / 100
1 ms332 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define F first #define S second ll n, A[1000001], B[1000001]; bool dp[4001][2001][2]; void p(bool zf){ if(zf==0)cout << 'A'; else cout << 'B'; return ; } void dfs(ll xf, ll yf, ll zf){ p(zf); if(xf==0){ return; } if(zf==0){ if((A[xf]>=A[xf-1]&&dp[xf-1][yf][0])){ dfs(xf-1, yf, 0); return; } if((A[xf]>=B[xf-1]&&dp[xf-1][yf][1])){ dfs(xf-1, yf, 1); return; } } else{ if((B[xf]>=A[xf-1]&&dp[xf-1][yf-1][0])){ dfs(xf-1, yf-1, 0); return; } if((B[xf]>=B[xf-1]&&dp[xf-1][yf-1][1])){ dfs(xf-1, yf-1, 1); return; } } return ; } int main(){ cin >> n; for(int i=0; i<2*n; i++){ cin >> A[i]; } for(int i=0; i<2*n; i++){ cin >> B[i]; } dp[0][0][0]=1; dp[0][1][1]=1; for(int i=1; i<2*n; i++){ for(int t=0; t<=n; t++){ if(t>0){ dp[i][t][1]=((B[i]>=A[i-1]&&dp[i-1][t-1][0])||(B[i]>=B[i-1]&&dp[i-1][t-1][1])); } dp[i][t][0]=((A[i]>=A[i-1]&&dp[i-1][t][0])||(A[i]>=B[i-1]&&dp[i-1][t][1])); } } if(dp[2*n-1][n][0]){ dfs(2*n-1, n, 0); } else if(dp[2*n-1][n][1]){ dfs(2*n-1, n, 1); } else{ cout << -1; } return 0; } /* 2 1 4 10 20 3 5 8 13 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...