oj.uz

Submission #623623

# Submission time Handle Problem Language Result Execution time Memory
623623 2022-08-06T06:31:55 Z CSQ31 Abduction 2 (JOI17_abduction2) C++17
27 / 100
 145 ms 31840 KB 
#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;
int dp[2][2000][2000];
int main()
{
	owo
	int h,w,q;
	cin>>h>>w>>q;
	if(min(h,w)<=2000){
		vector<pii>c;
		vector<int>a(h),b(w);
		for(int i=0;i<h;i++){
			cin>>a[i];
			c.push_back({a[i],i});
		}
		for(int i=0;i<w;i++){
			cin>>b[i];
			c.push_back({b[i],i});
		}
		sort(c.begin(),c.end(),greater<pii>());
		for(auto x:c){
			//cout<<x.fi<<" "<<x.se<<'\n';
			if(a[x.se] == x.fi){
				int i = x.se;
				int last = -1;
				for(int j=0;j<w;j++){
					if(last==-1)dp[0][i][j] = max(dp[0][i][j],j);
					else dp[0][i][j] = max(dp[0][i][j],j-last + dp[1][i][last]);
					if(b[j] > x.fi)last = j;
				}
				last = -1;
				for(int j=w-1;j>=0;j--){
					if(last==-1)dp[0][i][j] = max(dp[0][i][j],w-j-1);
					else dp[0][i][j] = max(dp[0][i][j],last-j + dp[1][i][last]);
					if(b[j] > x.fi)last = j;
				}
			}else{
				int j = x.se;
				int last = -1;
				for(int i=0;i<h;i++){
					if(last==-1)dp[1][i][j] = max(dp[1][i][j],i);
					else dp[1][i][j] = max(dp[1][i][j],i-last + dp[0][last][j]);
					if(a[i] > x.fi)last = i;
					
				}
				last = -1;
				for(int i=h-1;i>=0;i--){
					if(last==-1)dp[1][i][j] = max(dp[1][i][j],h-1-i);
					else dp[1][i][j] = max(dp[1][i][j],last-i + dp[0][last][j]);
					if(a[i] > x.fi)last = i;
				}
			}
			
			
		}
		/*
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++)cout<<dp[0][i][j]<<" ";
			cout<<'\n';
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++)cout<<dp[1][i][j]<<" ";
			cout<<'\n';
		}		*/
		while(q--){
			int i,j;
			cin>>i>>j;
			i--;
			j--;
			cout<<max(dp[0][i][j],dp[1][i][j])<<'\n';
		}
	}
	
	
	
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 122 ms 31688 KB Output is correct
13 Correct 126 ms 31736 KB Output is correct
14 Correct 123 ms 31624 KB Output is correct
15 Correct 131 ms 31728 KB Output is correct
16 Correct 122 ms 31696 KB Output is correct
17 Correct 91 ms 31664 KB Output is correct
18 Correct 88 ms 31692 KB Output is correct
19 Correct 109 ms 31788 KB Output is correct
20 Correct 104 ms 30712 KB Output is correct
21 Correct 95 ms 31692 KB Output is correct
22 Correct 99 ms 31732 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 122 ms 31688 KB Output is correct
13 Correct 126 ms 31736 KB Output is correct
14 Correct 123 ms 31624 KB Output is correct
15 Correct 131 ms 31728 KB Output is correct
16 Correct 122 ms 31696 KB Output is correct
17 Correct 91 ms 31664 KB Output is correct
18 Correct 88 ms 31692 KB Output is correct
19 Correct 109 ms 31788 KB Output is correct
20 Correct 104 ms 30712 KB Output is correct
21 Correct 95 ms 31692 KB Output is correct
22 Correct 99 ms 31732 KB Output is correct
23 Incorrect 0 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 31688 KB Output is correct
2 Correct 133 ms 31840 KB Output is correct
3 Correct 127 ms 31656 KB Output is correct
4 Correct 145 ms 31716 KB Output is correct
5 Correct 125 ms 31692 KB Output is correct
6 Correct 91 ms 31620 KB Output is correct
7 Correct 95 ms 31712 KB Output is correct
8 Correct 110 ms 31636 KB Output is correct
9 Correct 106 ms 31152 KB Output is correct
10 Correct 102 ms 31648 KB Output is correct
11 Correct 104 ms 31748 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 122 ms 31688 KB Output is correct
13 Correct 126 ms 31736 KB Output is correct
14 Correct 123 ms 31624 KB Output is correct
15 Correct 131 ms 31728 KB Output is correct
16 Correct 122 ms 31696 KB Output is correct
17 Correct 91 ms 31664 KB Output is correct
18 Correct 88 ms 31692 KB Output is correct
19 Correct 109 ms 31788 KB Output is correct
20 Correct 104 ms 30712 KB Output is correct
21 Correct 95 ms 31692 KB Output is correct
22 Correct 99 ms 31732 KB Output is correct
23 Incorrect 0 ms 340 KB Output isn't correct
24 Halted 0 ms 0 KB -