5574 | 2023-08-01 14:28:15 | 111 | Mágikus táblázat | cpp14 | Időlimit túllépés 41/100 | 600ms | 7612 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1684 KiB | ||||
2 | Elfogadva | 428ms | 2544 KiB | ||||
subtask2 | 14/14 | ||||||
3 | Elfogadva | 3ms | 2064 KiB | ||||
4 | Elfogadva | 3ms | 2300 KiB | ||||
5 | Elfogadva | 3ms | 2552 KiB | ||||
6 | Elfogadva | 3ms | 2728 KiB | ||||
7 | Elfogadva | 3ms | 2912 KiB | ||||
8 | Elfogadva | 3ms | 2992 KiB | ||||
subtask3 | 27/27 | ||||||
9 | Elfogadva | 8ms | 3304 KiB | ||||
10 | Elfogadva | 8ms | 3260 KiB | ||||
11 | Elfogadva | 8ms | 3444 KiB | ||||
12 | Elfogadva | 8ms | 3764 KiB | ||||
13 | Elfogadva | 4ms | 3824 KiB | ||||
14 | Elfogadva | 4ms | 3852 KiB | ||||
15 | Elfogadva | 6ms | 4120 KiB | ||||
16 | Elfogadva | 8ms | 4352 KiB | ||||
17 | Elfogadva | 8ms | 4656 KiB | ||||
subtask4 | 0/21 | ||||||
18 | Időlimit túllépés | 600ms | 6900 KiB | ||||
19 | Időlimit túllépés | 558ms | 6840 KiB | ||||
20 | Időlimit túllépés | 552ms | 6992 KiB | ||||
21 | Időlimit túllépés | 556ms | 7152 KiB | ||||
22 | Időlimit túllépés | 561ms | 6740 KiB | ||||
23 | Időlimit túllépés | 565ms | 6920 KiB | ||||
24 | Elfogadva | 7ms | 4972 KiB | ||||
subtask5 | 0/38 | ||||||
25 | Időlimit túllépés | 600ms | 7188 KiB | ||||
26 | Időlimit túllépés | 565ms | 7116 KiB | ||||
27 | Időlimit túllépés | 561ms | 7028 KiB | ||||
28 | Időlimit túllépés | 565ms | 6952 KiB | ||||
29 | Időlimit túllépés | 582ms | 7000 KiB | ||||
30 | Időlimit túllépés | 564ms | 7308 KiB | ||||
31 | Időlimit túllépés | 582ms | 7296 KiB | ||||
32 | Időlimit túllépés | 573ms | 6380 KiB | ||||
33 | Időlimit túllépés | 565ms | 6208 KiB | ||||
34 | Időlimit túllépés | 549ms | 6528 KiB | ||||
35 | Időlimit túllépés | 518ms | 6472 KiB | ||||
36 | Időlimit túllépés | 554ms | 7580 KiB | ||||
37 | Időlimit túllépés | 556ms | 7548 KiB | ||||
38 | Időlimit túllépés | 569ms | 7552 KiB | ||||
39 | Időlimit túllépés | 550ms | 7536 KiB | ||||
40 | Időlimit túllépés | 558ms | 7356 KiB | ||||
41 | Időlimit túllépés | 582ms | 6808 KiB | ||||
42 | Időlimit túllépés | 574ms | 7416 KiB | ||||
43 | Időlimit túllépés | 558ms | 7528 KiB | ||||
44 | Időlimit túllépés | 550ms | 7612 KiB |