#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef LOCAL
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 mt(time(0));
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#else
freopen("input.txt", "r", stdin);
#endif
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
void init() {}
#define int ll
void solve() {
int h, w;
cin >> h >> w;
vector<pair<ll, ll>> a1(h), b1(w), a, b, af, bf, as, bs;
for (int i = 0; i < h; i++) {
cin >> a1[i].x;
a1[i].y = 1;
}
for (int i = 0; i < w; i++) {
cin >> b1[i].x;
b1[i].y = 1;
}
for (int i = 0; i < h; i++) {
while (a.size() >= 2) {
auto ff = a.back();
a.pop_back();
if (!(a1[i].x <= ff.x && a.back().x <= ff.x)) {
a.push_back(ff);
break;
} else {
a.back().y += ff.y;
}
}
a.push_back(a1[i]);
}
for (int i = 0; i < w; i++) {
while (b.size() >= 2) {
auto ff = b.back();
b.pop_back();
if (!(b1[i].x <= ff.x && b.back().x <= ff.x)) {
b.push_back(ff);
break;
} else {
b.back().y += ff.y;
}
}
b.push_back(b1[i]);
}
ll ans = 0;
h = a.size();
w = b.size();
af.push_back(a[0]);
bf.push_back(b[0]);
for (int i = 1; i < h; i++) {
if (a[i] > a[i - 1]) {
as.push_back(a[i]);
} else {
af.push_back(a[i]);
}
}
for (int i = 1; i < w; i++) {
if (b[i] > b[i - 1]) {
bs.push_back(b[i]);
} else {
bf.push_back(b[i]);
}
}
// as.insert(as.begin(), af.back());
// bs.insert(bs.begin(), bf.back());
reverse(all(as));
reverse(all(bs));
as.push_back(af.back());
bs.push_back(bf.back());
for (int i = 0; i < as.size(); i++) {
as[i].y = as[(i + 1) % as.size()].y;
}
for (int i = 0; i < bs.size(); i++) {
bs[i].y = bs[(i + 1) % bs.size()].y;
}
// for (auto i : a) {
// cout << i.x << ' ';
// }
// cout << '\n';
// for (auto i : b) {
// cout << i.x << ' ';
// }
// cout << '\n';
// for (auto i : af) {
// cout << i.x << ' ';
// }
// cout << '\n';
// for (auto i : bf) {
// cout << i.x << ' ';
// }
// cout << '\n';
// for (auto i : as) {
// cout << i.x << ' ';
// }
// cout << '\n';
// for (auto i : bs) {
// cout << i.x << ' ';
// }
// cout << '\n';
// a = af;
a.clear();
for (int i = 0; i < af.size(); i++) {
while (a.size() >= 2) {
auto ff = a.back();
a.pop_back();
if (!(ff.x - af[i].x >= a.back().x - ff.x)) {
a.push_back(ff);
break;
} else {
a.back().y += ff.y;
}
}
a.push_back(af[i]);
}
// b = bf;
b.clear();
for (int i = 0; i < bf.size(); i++) {
while (b.size() >= 2) {
auto ff = b.back();
b.pop_back();
if (!(ff.x - bf[i].x >= b.back().x - ff.x)) {
b.push_back(ff);
break;
} else {
b.back().y += ff.y;
}
}
b.push_back(bf[i]);
}
h = a.size();
w = b.size();
vector<vector<ll>> dp(h + 1, vector<ll>(w + 1, INT64_MAX));
dp[0][0] = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b[j].x * a[i].y);
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + a[i].x * b[j].y);
}
}
ans += dp[h - 1][w - 1];
// cout << dp[h - 1][w - 1] << '\n';
a.clear();
for (int i = 0; i < as.size(); i++) {
while (a.size() >= 2) {
auto ff = a.back();
a.pop_back();
if (!(ff.x - as[i].x >= a.back().x - ff.x)) {
a.push_back(ff);
break;
} else {
a.back().y += ff.y;
}
}
a.push_back(as[i]);
}
// b = bf;
b.clear();
for (int i = 0; i < bs.size(); i++) {
while (b.size() >= 2) {
auto ff = b.back();
b.pop_back();
if (!(ff.x - bs[i].x >= b.back().x - ff.x)) {
b.push_back(ff);
break;
} else {
b.back().y += ff.y;
}
}
b.push_back(bs[i]);
}
h = a.size();
w = b.size();
dp.resize(h + 1);
for (int i = 0; i < h + 1; i++) {
dp[i].resize(w + 1);
for (int j = 0; j < w + 1; j++) {
dp[i][j] = INT64_MAX;
}
}
dp[0][0] = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + b[j].x * a[i].y);
dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + a[i].x * b[j].y);
}
}
ans += dp[h - 1][w - 1];
// cout << dp[h - 1][w - 1] << '\n';
cout << ans << '\n';
}
Compilation message
kyoto.cpp: In function 'void solve()':
kyoto.cpp:108:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for (int i = 0; i < as.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:111:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < bs.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:140:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int i = 0; i < af.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:155:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
155 | for (int i = 0; i < bf.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:181:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int i = 0; i < as.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:196:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for (int i = 0; i < bs.size(); i++) {
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
