Submission #212153

#TimeUsernameProblemLanguageResultExecution timeMemory
212153losmi247Building 4 (JOI20_building4)C++14
0 / 100
6 ms512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2005; int n,a[N],b[N]; bool dp[4005][2005][2]; void resimali(){ dp[1][0][1] = dp[1][1][0] = 1; for(int i = 2; i <= 2*n; i++){ for(int j = 0; j <= n; j++){ /// br A-ova if(a[i-1] <= a[i] && j >= 1){ dp[i][j][0] |= dp[i-1][j-1][0]; } if(b[i-1] <= a[i] && j >= 1){ dp[i][j][0] |= dp[i-1][j-1][1]; } if(a[i-1] <= b[i]){ dp[i][j][1] |= dp[i-1][j][0]; } if(b[i-1] <= b[i]){ dp[i][j][1] |= dp[i-1][j][1]; } } } if(!dp[2*n][n][0] && !dp[2*n][n][1]){ cout << -1 << endl; return; } int i = 2*n,j = n,k = -1; string ans; a[2*n+1] = b[2*n+1] = 2000000000; while(i){ if(dp[i][j][0] && a[i] <= (k == 0 ? a[i+1] : b[i+1])){ k = 0; } else{ k = 1; } if(k == 0){ ans += 'A'; j--; } else{ ans += 'B'; } i--; } reverse(ans.begin(),ans.end()); cout << ans << endl; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= 2*n; i++){ cin >> a[i]; } for(int i = 1; i <= 2*n; i++){ cin >> b[i]; } if(n <= 2000){ resimali(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...