Submission #1205544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205544		avighna	Building 4 (JOI20_building4)	C11	11 / 100	33 ms	16052 KiB

building4

#include <stdio.h>
#include <stdbool.h>

// #define N 500001
#define N 2001

int a[N << 1], b[N << 1];
bool dp[N << 1][N][2];
char res[N << 1];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= 2 * n; ++i) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= 2 * n; ++i) {
    scanf("%d", &b[i]);
  }

  dp[0][0][0] = dp[0][0][1] = true;
  int *arr[] = {b, a};
  for (int i = 1; i <= n << 1; ++i) {
    for (int j = 0; j <= n; ++j) {
      for (int k = 0; k < 2; ++k) {
        if (j - k >= 0) {
          dp[i][j][k] = (dp[i - 1][j - k][1] && a[i - 1] <= arr[k][i]) || (dp[i - 1][j - k][0] && b[i - 1] <= arr[k][i]);
        }
      }
    }
  }

  if (!dp[n << 1][n][0] && !dp[n << 1][n][1]) {
    printf("-1\n");
    return 0;
  }
  for (int i = n << 1, j = n, k = dp[n << 1][n][1]; i >= 1; --i) {
    res[i] = 'B' - k;
    if (dp[i - 1][j - k][1] && a[i - 1] <= arr[k][i]) {
      j -= k, k = 1;
    } else {
      j -= k, k = 0;
    }
  }
  printf("%s\n", res + 1);
}

Compilation message (stderr)

building4.c: In function 'main':
building4.c:13:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
building4.c:15:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d", &a[i]);
      |     ^~~~~~~~~~~~~~~~~~
building4.c:18:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d", &b[i]);
      |     ^~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 89