Submission #756936

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
756936	2023-06-12T11:28:25 Z	Dan4Life	Building 4 (JOI20_building4)	C++17	11 / 100	43 ms	16180 KB

building4

#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)2e3+10;
int n, a[2][mxN*2];
bool dp[mxN*2][mxN][2];
 
int main(){
    cin >> n;
    for(int i = 1; i<=2*n; i++) cin >> a[0][i];
    for(int i = 1; i<=2*n; i++) cin >> a[1][i];
    dp[1][0][0]=dp[1][1][1] = 1;
    for(int i = 2; i <= 2*n; i++)
        for(int j = 0; j <= n; j++)
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++)
                    if(a[l][i-1]<=a[k][i] and j>=!!k) 
                        dp[i][j][k]|=dp[i-1][j-!!k][l];
    int tot = n, p=(int)1e9+10; string ans = "";
    for(int i = 2*n; i; i--){
        for(int k = 0; k < 2; k++){
            if(dp[i][tot][k] and a[k][i]<=p){
                tot-=!!k; ans+=(k?'B':'A'); p=a[k][i]; break;
            }
        }
        if(i==2*n and ans.empty()){cout<<-1;return 0;}
    }
    reverse(begin(ans),end(ans)); cout << ans << "\n";
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	304 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	35 ms	14492 KB	Output is correct
6	Correct	31 ms	14508 KB	Output is correct
7	Correct	25 ms	12884 KB	Output is correct
8	Correct	31 ms	13908 KB	Output is correct
9	Correct	30 ms	14268 KB	Output is correct
10	Correct	25 ms	12708 KB	Output is correct
11	Correct	33 ms	15156 KB	Output is correct
12	Correct	36 ms	16076 KB	Output is correct
13	Correct	38 ms	16180 KB	Output is correct
14	Correct	41 ms	16128 KB	Output is correct
15	Correct	43 ms	16036 KB	Output is correct
16	Correct	42 ms	16076 KB	Output is correct
17	Correct	38 ms	16052 KB	Output is correct
18	Correct	39 ms	16136 KB	Output is correct
19	Correct	37 ms	16028 KB	Output is correct
20	Correct	37 ms	16056 KB	Output is correct
21	Correct	36 ms	16040 KB	Output is correct
22	Correct	38 ms	16052 KB	Output is correct
23	Correct	37 ms	16060 KB	Output is correct
24	Correct	37 ms	16028 KB	Output is correct
25	Correct	35 ms	15980 KB	Output is correct
26	Correct	35 ms	16112 KB	Output is correct
27	Correct	35 ms	16072 KB	Output is correct
28	Correct	31 ms	14372 KB	Output is correct
29	Correct	36 ms	16088 KB	Output is correct
30	Correct	31 ms	14392 KB	Output is correct
31	Correct	35 ms	16088 KB	Output is correct
32	Correct	27 ms	13512 KB	Output is correct
33	Correct	35 ms	16016 KB	Output is correct

Subtask #2

0 / 89.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	308 KB	Output is correct
3	Correct	1 ms	304 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	35 ms	14492 KB	Output is correct
6	Correct	31 ms	14508 KB	Output is correct
7	Correct	25 ms	12884 KB	Output is correct
8	Correct	31 ms	13908 KB	Output is correct
9	Correct	30 ms	14268 KB	Output is correct
10	Correct	25 ms	12708 KB	Output is correct
11	Correct	33 ms	15156 KB	Output is correct
12	Correct	36 ms	16076 KB	Output is correct
13	Correct	38 ms	16180 KB	Output is correct
14	Correct	41 ms	16128 KB	Output is correct
15	Correct	43 ms	16036 KB	Output is correct
16	Correct	42 ms	16076 KB	Output is correct
17	Correct	38 ms	16052 KB	Output is correct
18	Correct	39 ms	16136 KB	Output is correct
19	Correct	37 ms	16028 KB	Output is correct
20	Correct	37 ms	16056 KB	Output is correct
21	Correct	36 ms	16040 KB	Output is correct
22	Correct	38 ms	16052 KB	Output is correct
23	Correct	37 ms	16060 KB	Output is correct
24	Correct	37 ms	16028 KB	Output is correct
25	Correct	35 ms	15980 KB	Output is correct
26	Correct	35 ms	16112 KB	Output is correct
27	Correct	35 ms	16072 KB	Output is correct
28	Correct	31 ms	14372 KB	Output is correct
29	Correct	36 ms	16088 KB	Output is correct
30	Correct	31 ms	14392 KB	Output is correct
31	Correct	35 ms	16088 KB	Output is correct
32	Correct	27 ms	13512 KB	Output is correct
33	Correct	35 ms	16016 KB	Output is correct
34	Runtime error	4 ms	724 KB	Execution killed with signal 11
35	Halted	0 ms	0 KB	-