#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
typedef long long ll;
ll n, m, a[MAXN], b[MAXN];
ll mnp[MAXN][2], mns[MAXN][2];
vector <ll> remx = {0}, remy = {0};
ll dp[3001][3001];
int main () {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mnp[i][0] = mns[i][1] = a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
mns[i][0] = mns[i][1] = b[i];
}
for (int i = 1; i <= n; i++) {
mnp[i][0] = min(mnp[i][0], mnp[i - 1][0]);
}
for (int i = 1; i <= m; i++) {
mnp[i][1] = min(mnp[i][1], mnp[i - 1][1]);
}
for (int i = n - 1; i >= 1; i--) {
mns[i][0] = min(mns[i][0], mns[i + 1][0]);
}
for (int i = m - 1; i >= 1; i--) {
mns[i][1] = min(mns[i][1], mns[i + 1][1]);
}
for (int i = 1; i <= n; i++) {
bool flag = i > 1 && a[i] >= mnp[i][0];
flag &= i < n && a[i] >= mns[i][0];
if (flag) continue;
remx.push_back(i);
}
for (int i = 1; i <= m; i++) {
bool flag = i > 1 && b[i] >= mnp[i][1];
flag &= i < m && b[i] >= mns[i][1];
if (flag) continue;
remy.push_back(i);
}
for (int i = 1; i < (int)remx.size(); i++) {
for (int j = 1; j < (int)remy.size(); j++) {
if (i == j && j == 1) continue;
dp[i][j] = 1e18;
if (i > 1) dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[remy[j]] * (remx[i] - remx[i - 1]));
if (j > 1) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[remx[i]] * (remy[i] - remy[i - 1]));
}
}
cout << dp[(int)remx.size() - 1][(int)remy.size() - 1] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
