Submission #623623

#	Time	Username	Problem	Language	Result	Execution time	Memory
623623		CSQ31	Abduction 2 (JOI17_abduction2)	C++17	27 / 100	145 ms	31840 KiB

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;
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 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56