Submission #414914

#TimeUsernameProblemLanguageResultExecution timeMemory
414914Pro_ktmrBuilding 4 (JOI20_building4)C++17
100 / 100
562 ms90248 KiB
#include"bits/stdc++.h" using namespace std; typedef long long ll; const ll MOD = (ll)(1e9+7); #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++) const int INF = 1e9; int N; int A[1'000'000], B[1'000'000]; // A の数を最大化 int dpA[1'000'000][2]; int solveA(int n, int l){ if(n == 2*N) return 0; if(n == 0) return max(solveA(1, 0)+1, solveA(1, 1)); if(dpA[n][l] != -1) return dpA[n][l]; int ret = -INF; if(l == 0){ if(A[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1); if(A[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1)); } else{ if(B[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1); if(B[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1)); } return dpA[n][l] = ret; } // B の数を最大化 int dpB[1'000'000][2]; int solveB(int n, int l){ if(n == 2*N) return 0; if(n == 0) return max(solveB(1, 0), solveB(1, 1)+1); if(dpB[n][l] != -1) return dpB[n][l]; int ret = -INF; if(l == 0){ if(A[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0)); if(A[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1); } else{ if(B[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0)); if(B[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1); } return dpB[n][l] = ret; } void print(int n, int a, int l){ if(l == 0) printf("A"); if(l == 1) printf("B"); if(n == 2*N) return; if(n == 0){ if(solveA(1, 0) >= N-1 && solveB(1, 0) >= N){ print(n+1, a+1, 0); return; } if(solveA(1, 1) >= N && solveB(1, 1) >= N-1){ print(n+1, a, 1); return; } } int b = n-a; if(l == 0){ if(A[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){ print(n+1, a+1, 0); return; } if(A[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){ print(n+1, a, 1); return; } } else{ if(B[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){ print(n+1, a+1, 0); return; } if(B[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){ print(n+1, a, 1); return; } } } signed main(){ scanf("%d", &N); rep(i, 2*N) scanf("%d", A+i); rep(i, 2*N) scanf("%d", B+i); memset(dpA, -1, sizeof(dpA)); memset(dpB, -1, sizeof(dpB)); if(solveA(0, -1) < N || solveB(0, -1) < N){ printf("-1\n"); return 0; } print(0, 0, -1); printf("\n"); }

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
building4.cpp:95:2: note: in expansion of macro 'rep'
   95 |  rep(i, 2*N) scanf("%d", A+i);
      |  ^~~
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
building4.cpp:96:2: note: in expansion of macro 'rep'
   96 |  rep(i, 2*N) scanf("%d", B+i);
      |  ^~~
building4.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
building4.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |  rep(i, 2*N) scanf("%d", A+i);
      |              ~~~~~^~~~~~~~~~~
building4.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  rep(i, 2*N) scanf("%d", B+i);
      |              ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...