제출 #240627

#제출 시각아이디문제언어결과실행 시간메모리
240627sven건물 4 (JOI20_building4)C++14
11 / 100
477 ms273472 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAXN = 2001; int prec[MAXN * 2][MAXN][2]; int A[MAXN * 2]; int B[MAXN * 2]; int N; void dp(int posActu , int score , int iEtage) { //cout<<posActu<<" "<<score<<" "<<iEtage<<endl; if (posActu == 2 * N -1) { return; } if (iEtage == 0) { if (score < N && prec[posActu + 1][score + 1][0] == -1 && A[posActu] <= A[posActu + 1]) { // cout<<"QergqreGQ"<<endl; prec[posActu + 1][score + 1][0] = 1; dp(posActu + 1 , score + 1 , 0); } if (prec[posActu + 1][score][1] == -1 && A[posActu] <= B[posActu + 1]) { prec[posActu + 1][score][1] = 2; dp(posActu + 1 , score , 1); } } else { if (score < N && prec[posActu + 1][score + 1][0] == -1 && B[posActu] <= A[posActu + 1]) { // cout<<"QeroogqreGQ"<<endl; prec[posActu + 1][score + 1][0] = 2; dp(posActu + 1 , score + 1 , 0); } if (prec[posActu + 1][score][1] == -1 && B[posActu] <= B[posActu + 1]) { prec[posActu + 1][score][1] = 1; dp(posActu + 1 , score , 1); } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N; for (int i = 0 ; i < N * 2 ; i++) { cin >> A[i]; } for (int i = 0 ; i < N * 2 ; i++) { cin >> B[i]; } for (int i = 0 ; i < MAXN * 2 ; i++) { for (int j = 0 ; j < MAXN ; j++) { prec[i][j][0] = prec[i][j][1] = -1; } } dp(0 , 1 , 0); dp(0 , 0 , 1); int posActu = 0; if (prec[2 * N - 1][N][0] != -1) { posActu = 0; } else if (prec[2* N - 1][N][1] != -1) { posActu = 1; } else { cout<<-1<<endl; exit(0); } vector <int> sol; int scoreActu = N; for (int i = 0 ; i < 2 * N ; i++) { //cout<<i<<" e"<<posActu<<" "<<scoreActu<<" "<<prec[2 * N -1 - i][scoreActu][posActu]<<" "<<2 * N - 1 - i<<endl; sol.push_back(posActu); if (i < 2 * N - 1) { int pp = posActu; if (prec[2 * N - 1 - i][scoreActu][posActu] == 2) { // cout<<"a"<<endl; posActu = 1 - posActu; } scoreActu -= (pp == 0); } } for (int i = 2 * N -1 ; i >= 0 ; i--) { if (sol[i] == 0) cout<<"A"; else cout<<"B"; } cout<<endl; /*for (int k = 0 ; k < 2 ; k++) { for (int i = 0 ; i < 2 * N ; i++) { for (int j = 0 ; j <= N ; j++) { cout<<prec[i][j][k]<<" "; } cout<<endl; } cout<<endl; }*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...