답안 #624798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624798	2022-08-08T18:21:22 Z	CSQ31	유괴 2 (JOI17_abduction2)	C++17	44 / 100	1171 ms	15208 KB

abduction2

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
const int MAXN = 55555;
int a[MAXN],b[MAXN];
int hmx[2][MAXN],wmx[2][MAXN];
int h,w,q;
typedef long long int ll;
map<int,ll>dp[2][MAXN];
ll solve(ll i,ll j,ll k){
	if(dp[k][i].find(j) != dp[k][i].end())return dp[k][i][j];
	if(!k){
		dp[0][i][j] = -1e9;
		for(ll jj=j+1;jj<w;jj++){
			if(b[jj] > a[i]){
				dp[0][i][j] = max(dp[0][i][j],solve(i,jj,1)+jj-j);
				break;
			}
		}
		for(ll jj=j-1;jj>=0;jj--){
			if(b[jj] > a[i]){
				dp[0][i][j] = max(dp[0][i][j],solve(i,jj,1)+j-jj);
				break;
			}
		}
		if(dp[0][i][j] == -1e9)dp[0][i][j] = max(w-1-j,j);
	}else{
		dp[1][i][j] = -1e9;
		for(ll ii=i+1;ii<h;ii++){
			if(a[ii] > b[j]){
				dp[1][i][j] = max(dp[1][i][j],solve(ii,j,0) + ii-i);
				break;
			}
		}
		for(ll ii=i-1;ii>=0;ii--){
			if(a[ii] > b[j]){
				dp[1][i][j] = max(dp[1][i][j],solve(ii,j,0) + i-ii);
				break;
			}
		}
		if(dp[1][i][j] == -1e9)dp[1][i][j] = max(h-1-i,i);
	}
	return dp[k][i][j];
}
int main()
{
	owo
	cin>>h>>w>>q;
	for(int i=0;i<h;i++)cin>>a[i];
	for(int i=0;i<w;i++)cin>>b[i];
	for(int i=0;i<h;i++){
		hmx[0][i] = a[i];
		if(i)hmx[0][i] = max(hmx[0][i],hmx[0][i-1]);
	}
	for(int i=h-1;i>=0;i--){
		hmx[1][i] = a[i];
		if(i!=h-1)hmx[1][i] = max(hmx[1][i],hmx[1][i+1]);
	}
	for(int i=0;i<w;i++){
		wmx[0][i] = b[i];
		if(i)wmx[0][i] = max(wmx[0][i],wmx[0][i-1]);
	}
	for(int i=w-1;i>=0;i--){
		wmx[1][i] = b[i];
		if(i!=w-1)wmx[1][i] = max(wmx[1][i],wmx[1][i+1]);
	}
	while(q--){
		int i,j;
		cin>>i>>j;
		i--;
		j--;
		ll ans = max(solve(i,j,0),solve(i,j,1));
		cout<<ans<<'\n';
	}
	
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5460 KB	Output is correct
2	Correct	3 ms	5460 KB	Output is correct
3	Correct	3 ms	5460 KB	Output is correct
4	Correct	3 ms	5460 KB	Output is correct
5	Correct	3 ms	5460 KB	Output is correct
6	Correct	2 ms	5460 KB	Output is correct
7	Correct	3 ms	5460 KB	Output is correct
8	Correct	2 ms	5460 KB	Output is correct
9	Correct	3 ms	5460 KB	Output is correct
10	Correct	3 ms	5468 KB	Output is correct
11	Correct	3 ms	5460 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5460 KB	Output is correct
2	Correct	3 ms	5460 KB	Output is correct
3	Correct	3 ms	5460 KB	Output is correct
4	Correct	3 ms	5460 KB	Output is correct
5	Correct	3 ms	5460 KB	Output is correct
6	Correct	2 ms	5460 KB	Output is correct
7	Correct	3 ms	5460 KB	Output is correct
8	Correct	2 ms	5460 KB	Output is correct
9	Correct	3 ms	5460 KB	Output is correct
10	Correct	3 ms	5468 KB	Output is correct
11	Correct	3 ms	5460 KB	Output is correct
12	Correct	3 ms	5540 KB	Output is correct
13	Correct	3 ms	5588 KB	Output is correct
14	Correct	4 ms	5588 KB	Output is correct
15	Correct	3 ms	5588 KB	Output is correct
16	Correct	3 ms	5588 KB	Output is correct
17	Correct	3 ms	5588 KB	Output is correct
18	Correct	4 ms	5632 KB	Output is correct
19	Correct	5 ms	5716 KB	Output is correct
20	Correct	6 ms	5844 KB	Output is correct
21	Correct	5 ms	5844 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5460 KB	Output is correct
2	Correct	3 ms	5460 KB	Output is correct
3	Correct	3 ms	5460 KB	Output is correct
4	Correct	3 ms	5460 KB	Output is correct
5	Correct	3 ms	5460 KB	Output is correct
6	Correct	2 ms	5460 KB	Output is correct
7	Correct	3 ms	5460 KB	Output is correct
8	Correct	2 ms	5460 KB	Output is correct
9	Correct	3 ms	5460 KB	Output is correct
10	Correct	3 ms	5468 KB	Output is correct
11	Correct	3 ms	5460 KB	Output is correct
12	Correct	3 ms	5540 KB	Output is correct
13	Correct	3 ms	5588 KB	Output is correct
14	Correct	4 ms	5588 KB	Output is correct
15	Correct	3 ms	5588 KB	Output is correct
16	Correct	3 ms	5588 KB	Output is correct
17	Correct	3 ms	5588 KB	Output is correct
18	Correct	4 ms	5632 KB	Output is correct
19	Correct	5 ms	5716 KB	Output is correct
20	Correct	6 ms	5844 KB	Output is correct
21	Correct	5 ms	5844 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	12 ms	6640 KB	Output is correct
24	Correct	12 ms	6632 KB	Output is correct
25	Correct	13 ms	6676 KB	Output is correct
26	Correct	13 ms	6740 KB	Output is correct
27	Correct	12 ms	6656 KB	Output is correct
28	Correct	465 ms	12364 KB	Output is correct
29	Correct	90 ms	7528 KB	Output is correct
30	Correct	1069 ms	13256 KB	Output is correct
31	Correct	1171 ms	15208 KB	Output is correct
32	Correct	86 ms	6992 KB	Output is correct
33	Correct	397 ms	8876 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5716 KB	Output is correct
2	Correct	5 ms	5716 KB	Output is correct
3	Correct	4 ms	5716 KB	Output is correct
4	Correct	5 ms	5716 KB	Output is correct
5	Correct	4 ms	5716 KB	Output is correct
6	Correct	4 ms	5844 KB	Output is correct
7	Correct	5 ms	5844 KB	Output is correct
8	Correct	6 ms	6044 KB	Output is correct
9	Correct	6 ms	6048 KB	Output is correct
10	Correct	6 ms	5972 KB	Output is correct
11	Correct	7 ms	6100 KB	Output is correct

Subtask #5
0 / 56.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5460 KB	Output is correct
2	Correct	3 ms	5460 KB	Output is correct
3	Correct	3 ms	5460 KB	Output is correct
4	Correct	3 ms	5460 KB	Output is correct
5	Correct	3 ms	5460 KB	Output is correct
6	Correct	2 ms	5460 KB	Output is correct
7	Correct	3 ms	5460 KB	Output is correct
8	Correct	2 ms	5460 KB	Output is correct
9	Correct	3 ms	5460 KB	Output is correct
10	Correct	3 ms	5468 KB	Output is correct
11	Correct	3 ms	5460 KB	Output is correct
12	Correct	3 ms	5540 KB	Output is correct
13	Correct	3 ms	5588 KB	Output is correct
14	Correct	4 ms	5588 KB	Output is correct
15	Correct	3 ms	5588 KB	Output is correct
16	Correct	3 ms	5588 KB	Output is correct
17	Correct	3 ms	5588 KB	Output is correct
18	Correct	4 ms	5632 KB	Output is correct
19	Correct	5 ms	5716 KB	Output is correct
20	Correct	6 ms	5844 KB	Output is correct
21	Correct	5 ms	5844 KB	Output is correct
22	Correct	7 ms	6100 KB	Output is correct
23	Correct	12 ms	6640 KB	Output is correct
24	Correct	12 ms	6632 KB	Output is correct
25	Correct	13 ms	6676 KB	Output is correct
26	Correct	13 ms	6740 KB	Output is correct
27	Correct	12 ms	6656 KB	Output is correct
28	Correct	465 ms	12364 KB	Output is correct
29	Correct	90 ms	7528 KB	Output is correct
30	Correct	1069 ms	13256 KB	Output is correct
31	Correct	1171 ms	15208 KB	Output is correct
32	Correct	86 ms	6992 KB	Output is correct
33	Correct	397 ms	8876 KB	Output is correct
34	Correct	4 ms	5716 KB	Output is correct
35	Correct	5 ms	5716 KB	Output is correct
36	Correct	4 ms	5716 KB	Output is correct
37	Correct	5 ms	5716 KB	Output is correct
38	Correct	4 ms	5716 KB	Output is correct
39	Correct	4 ms	5844 KB	Output is correct
40	Correct	5 ms	5844 KB	Output is correct
41	Correct	6 ms	6044 KB	Output is correct
42	Correct	6 ms	6048 KB	Output is correct
43	Correct	6 ms	5972 KB	Output is correct
44	Correct	7 ms	6100 KB	Output is correct
45	Correct	19 ms	7004 KB	Output is correct
46	Correct	18 ms	6936 KB	Output is correct
47	Correct	20 ms	7040 KB	Output is correct
48	Incorrect	19 ms	7000 KB	Output isn't correct
49	Halted	0 ms	0 KB	-

답안 #624798

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 10.0 / 10.0

Subtask #3 17.0 / 17.0

Subtask #4 4.0 / 4.0

Subtask #5 0 / 56.0

Subtask #1
13.0 / 13.0

Subtask #2
10.0 / 10.0

Subtask #3
17.0 / 17.0

Subtask #4
4.0 / 4.0

Subtask #5
0 / 56.0