Submission #205202

#	Time	Username	Problem	Language	Result	Execution time	Memory
205202		hanagasumi	Abduction 2 (JOI17_abduction2)	C++17	44 / 100	4165 ms	16092 KiB

abduction2

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
 
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll

using namespace std;
typedef long long ll;
typedef long double ld;

map<pair<int, int>, int> dp;
int w, h;
vector<int> a;
vector<int> b;


int solve(int i, int j) {
	// cout << a[i] << " " << b[j] << endl;
	if(dp.count({i, j})) 
		return dp[{i, j}];
	if(a[i] > b[j]) {
		int r = w;
		for (int now = j; now < w; now++) {
			if(b[now] > a[i]) {
				r = now;
				break;
			}
		}
		if(r == w) 
			dp[{i, j}] = max(dp[{i, j}], w - j);
		else
			dp[{i, j}] = max(dp[{i, j}], r - j + solve(i, r));

		int l = -1;
		for (int now = j; now >= 0; now--) {
			if(b[now] > a[i]) {
				l = now;
				break;
			}
		}
		if(l == -1) 
			dp[{i, j}] = max(dp[{i, j}], j + 1);
		else
			dp[{i, j}] = max(dp[{i, j}], j - l + solve(i, l));
	}
	else {
		int r = h;
		for (int now = i; now < h; now++) {
			if(a[now] > b[j]) {
				r = now;
				break;
			}
		}
		if(r == h) 
			dp[{i, j}] = max(dp[{i, j}], h - i);
		else
			dp[{i, j}] = max(dp[{i, j}], r - i + solve(r, j));

		int l = -1;
		for (int now = i; now >= 0; now--) {
			if(a[now] > b[j]) {
				l = now;
				break;
			}
		}
		if(l == -1) 
			dp[{i, j}] = max(dp[{i, j}], i + 1);
		else
			dp[{i, j}] = max(dp[{i, j}], i - l + solve(l, j));
	}
	return dp[{i, j}];
}


signed main() {
	#ifdef PC 
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int q;
	cin >> h >> w >> q;
	a = vector<int> (h);
	b = vector<int> (w);
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}
	for (int j = 0; j < w; j++) {
		cin >> b[j];
	}

	for (int k = 0; k < q; k++) {
		int i, j;
		cin >> i >> j;
		i--, j--;
		int ans = 1;
		for (int j1 = j + 1; j1 < w; j1++) {
			ans = max(ans, j1 - j + 1);
			if(b[j1] > a[i]) {
				ans = max(ans, j1 - j + solve(i, j1));
				break;
			}
		}
		for (int j1 = j - 1; j1 >= 0; j1--) {
			ans = max(ans, j - j1 + 1);
			if(b[j1] > a[i]) {
				ans = max(ans, j - j1 + solve(i, j1));
				break;
			}
		}


		for (int i1 = i + 1; i1 < h; i1++) {
			ans = max(ans, i1 - i + 1);
			if(a[i1] > b[j]) {
				ans = max(ans, i1 - i + solve(i1, j));
				break;
			}
		}
		for (int i1 = i - 1; i1 >= 0; i1--) {
			ans = max(ans, i - i1 + 1);
			if(a[i1] > b[j]) {
				ans = max(ans, i - i1 + solve(i1, j));
				break;
			}
		}

		cout << ans - 1 << '\n';
	}

}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56