5573 | 2023-08-01 14:09:00 | 111 | Mágikus táblázat | cpp14 | Time limit exceeded 41/100 | 600ms | 9192 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);
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, (na[i] - pa[i] - 1) * (nb[j] - pb[j] - 1));
}
}
cout << ans << endl;
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1812 KiB | ||||
2 | Accepted | 453ms | 3040 KiB | ||||
subtask2 | 14/14 | ||||||
3 | Accepted | 3ms | 2136 KiB | ||||
4 | Accepted | 3ms | 2348 KiB | ||||
5 | Accepted | 3ms | 2572 KiB | ||||
6 | Accepted | 3ms | 2820 KiB | ||||
7 | Accepted | 3ms | 2972 KiB | ||||
8 | Accepted | 3ms | 3204 KiB | ||||
subtask3 | 27/27 | ||||||
9 | Accepted | 9ms | 3628 KiB | ||||
10 | Accepted | 9ms | 3840 KiB | ||||
11 | Accepted | 9ms | 3880 KiB | ||||
12 | Accepted | 8ms | 3796 KiB | ||||
13 | Accepted | 4ms | 3764 KiB | ||||
14 | Accepted | 4ms | 3764 KiB | ||||
15 | Accepted | 8ms | 3908 KiB | ||||
16 | Accepted | 10ms | 3776 KiB | ||||
17 | Accepted | 8ms | 4036 KiB | ||||
subtask4 | 0/21 | ||||||
18 | Time limit exceeded | 600ms | 7776 KiB | ||||
19 | Time limit exceeded | 574ms | 7788 KiB | ||||
20 | Time limit exceeded | 552ms | 8180 KiB | ||||
21 | Time limit exceeded | 573ms | 8208 KiB | ||||
22 | Time limit exceeded | 561ms | 7844 KiB | ||||
23 | Time limit exceeded | 550ms | 7860 KiB | ||||
24 | Accepted | 7ms | 4900 KiB | ||||
subtask5 | 0/38 | ||||||
25 | Time limit exceeded | 600ms | 8576 KiB | ||||
26 | Time limit exceeded | 561ms | 8728 KiB | ||||
27 | Time limit exceeded | 546ms | 8628 KiB | ||||
28 | Time limit exceeded | 565ms | 8720 KiB | ||||
29 | Time limit exceeded | 561ms | 8544 KiB | ||||
30 | Time limit exceeded | 561ms | 8464 KiB | ||||
31 | Time limit exceeded | 561ms | 8828 KiB | ||||
32 | Time limit exceeded | 577ms | 7176 KiB | ||||
33 | Time limit exceeded | 504ms | 7312 KiB | ||||
34 | Time limit exceeded | 541ms | 7392 KiB | ||||
35 | Time limit exceeded | 565ms | 7372 KiB | ||||
36 | Time limit exceeded | 564ms | 9012 KiB | ||||
37 | Time limit exceeded | 554ms | 8860 KiB | ||||
38 | Time limit exceeded | 533ms | 8952 KiB | ||||
39 | Time limit exceeded | 580ms | 8960 KiB | ||||
40 | Time limit exceeded | 578ms | 8804 KiB | ||||
41 | Time limit exceeded | 541ms | 8044 KiB | ||||
42 | Time limit exceeded | 560ms | 8732 KiB | ||||
43 | Time limit exceeded | 533ms | 8936 KiB | ||||
44 | Time limit exceeded | 565ms | 9192 KiB |