55742023-08-01 14:28:15111Mágikus táblázatcpp14Időlimit túllépés 41/100600ms7612 KiB
#include <bits/extc++.h>
using namespace std;

//#define int long long

#define pii pair<int, int>

void prev_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = 0; i < a.size(); i++) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? -1 : s.top();
		s.push(i);
	}
}

void prev_less(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = 0; i < a.size(); i++) {
		while (!s.empty() && a[s.top()] >= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? -1 : s.top();
		s.push(i);
	}
}

void next_greater(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = a.size() - 1; i >= 0; i--) {
		while (!s.empty() && a[s.top()] <= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? a.size() : s.top();
		s.push(i);
	}
}

void next_less(vector<int>& r, const vector<int>& a) {
	stack<int> s;
	for (int i = a.size() - 1; i >= 0; i--) {
		while (!s.empty() && a[s.top()] >= a[i]) {
			s.pop();
		}
		r[i] = s.empty() ? a.size() : s.top();
		s.push(i);
	}
}

signed main() {
#ifdef CB
	ifstream fin("be2.txt");
	cin.rdbuf(fin.rdbuf());
	ofstream fout("ki.txt");
#endif
	int A, B;
	cin >> A >> B;
	vector<int> a(A), b(B);
	for (int i = 0; i < A; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < B; i++) {
		cin >> b[i];
	}
	vector<int> pa(A), na(A);
	vector<int> pb(B), nb(B);
	prev_less(pa, a);
	next_less(na, a);
	prev_greater(pb, b);
	next_greater(nb, b);
	vector<int> da(A), db(B);
	for (int i = 0; i < A; i++) {
		da[i] = na[i] - pa[i] - 1;
	}
	for (int i = 0; i < B; i++) {
		db[i] = nb[i] - pb[i] - 1;
	}
	int ans = 0;
	for (int i = 0; i < A; i++) {
		for (int j = 0; j < B; j++) {
			if (b[j] > a[i]) {
				continue;
			}
			ans = max(ans, da[i] * db[j]);
		}
	}
	cout << ans << endl;
	return 0;
}























RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1684 KiB
2Elfogadva428ms2544 KiB
subtask214/14
3Elfogadva3ms2064 KiB
4Elfogadva3ms2300 KiB
5Elfogadva3ms2552 KiB
6Elfogadva3ms2728 KiB
7Elfogadva3ms2912 KiB
8Elfogadva3ms2992 KiB
subtask327/27
9Elfogadva8ms3304 KiB
10Elfogadva8ms3260 KiB
11Elfogadva8ms3444 KiB
12Elfogadva8ms3764 KiB
13Elfogadva4ms3824 KiB
14Elfogadva4ms3852 KiB
15Elfogadva6ms4120 KiB
16Elfogadva8ms4352 KiB
17Elfogadva8ms4656 KiB
subtask40/21
18Időlimit túllépés600ms6900 KiB
19Időlimit túllépés558ms6840 KiB
20Időlimit túllépés552ms6992 KiB
21Időlimit túllépés556ms7152 KiB
22Időlimit túllépés561ms6740 KiB
23Időlimit túllépés565ms6920 KiB
24Elfogadva7ms4972 KiB
subtask50/38
25Időlimit túllépés600ms7188 KiB
26Időlimit túllépés565ms7116 KiB
27Időlimit túllépés561ms7028 KiB
28Időlimit túllépés565ms6952 KiB
29Időlimit túllépés582ms7000 KiB
30Időlimit túllépés564ms7308 KiB
31Időlimit túllépés582ms7296 KiB
32Időlimit túllépés573ms6380 KiB
33Időlimit túllépés565ms6208 KiB
34Időlimit túllépés549ms6528 KiB
35Időlimit túllépés518ms6472 KiB
36Időlimit túllépés554ms7580 KiB
37Időlimit túllépés556ms7548 KiB
38Időlimit túllépés569ms7552 KiB
39Időlimit túllépés550ms7536 KiB
40Időlimit túllépés558ms7356 KiB
41Időlimit túllépés582ms6808 KiB
42Időlimit túllépés574ms7416 KiB
43Időlimit túllépés558ms7528 KiB
44Időlimit túllépés550ms7612 KiB