Submission #535522

#	Time	Username	Problem	Language	Result	Execution time	Memory
535522		79brue	건물 4 (JOI20_building4)	C++14	100 / 100	280 ms	61204 KiB

building4

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int a[1000002][2];
int DP[1000002][2][2]; /// a/b, l/r
int track[1000002][2][2];

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n+n; i++) scanf("%d", &a[i][0]);
    for(int i=1; i<=n+n; i++) scanf("%d", &a[i][1]);
    for(int i=1; i<=n+n; i++){
        DP[i][0][0] = DP[i][1][0] = 1e9;
        for(int j=0; j<2; j++){
            for(int j2=0; j2<2; j2++){
                if(a[i-1][j2] <= a[i][j]){
                    if(DP[i][j][0] > DP[i-1][j2][0] + (j==0)){
                        DP[i][j][0] = DP[i-1][j2][0] + (j==0);
                        track[i][j][0] = j2;
                    }
                    if(DP[i][j][1] < DP[i-1][j2][1] + (j==0)){
                        DP[i][j][1] = DP[i-1][j2][1] + (j==0);
                        track[i][j][1] = j2;
                    }
                }
            }
        }
    }

    int i=0, j=0;
    if((DP[n+n][0][0] <= n && n <= DP[n+n][0][1])) i=n+n, j=0;
    else if(DP[n+n][1][0] <= n && n <= DP[n+n][1][1]) i=n+n, j=1;
    else{
        puts("-1");
        return 0;
    }

    string s;
    int cnt = n;
    while(i){
        if(j==0) s.push_back('A'), cnt--;
        else s.push_back('B');

        int c = 0;
        if(a[i][j] < a[i-1][0]) c = 1;
        else if(DP[i-1][0][0] > cnt || DP[i-1][0][1] < cnt) c = 1;
        j = c;
        i--;
    }
    reverse(s.begin(), s.end());
    printf("%s", s.c_str());
}

Compilation message (stderr)

building4.cpp: In function 'int main()':
building4.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
building4.cpp:14:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     for(int i=1; i<=n+n; i++) scanf("%d", &a[i][0]);
      |                               ~~~~~^~~~~~~~~~~~~~~~
building4.cpp:15:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     for(int i=1; i<=n+n; i++) scanf("%d", &a[i][1]);
      |                               ~~~~~^~~~~~~~~~~~~~~~

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