#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()
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[40000];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i * 4 + j] = n % 10 + '0';
n /= 10;
}
}
}
} constexpr pre;
__attribute__((target("avx2"), optimize("O3"))) inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
}
__attribute__((target("avx2"), optimize("O3"))) inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
inline void read(char &c) { c = ibuf[pil++]; }
template<typename T>
__attribute__((target("avx2"), optimize("O3"))) inline void read(T &x) {
if (pil + 32 > pir) load();
char c;
do
read(c);
while (c < '-');
bool minus = 0;
if (std::is_signed<T>::value) {
if (c == '-') {
minus = 1;
read(c);
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
read(c);
}
if (std::is_signed<T>::value) {
if (minus) x = -x;
}
}
inline void write(char c) { obuf[por++] = c; }
template<typename T>
__attribute__((target("avx2"), optimize("O3"))) inline void write(T x) {
if (por + 32 > SZ) flush();
if (!x) {
write('0');
return;
}
if (std::is_signed<T>::value) {
if (x < 0) {
write('-');
x = -x;
}
}
if (x >= 10000000000000000) {
uint32_t r1 = x % 100000000;
uint64_t q1 = x / 100000000;
uint32_t r2 = q1 % 100000000;
uint32_t q2 = q1 / 100000000;
uint32_t n1 = r1 % 10000;
uint32_t n2 = r1 / 10000;
uint32_t n3 = r2 % 10000;
uint32_t n4 = r2 / 10000;
if (x >= 1000000000000000000) {
uint32_t q3 = (q2 * 20972) >> 21;
uint32_t r3 = q2 - q3 * 100;
uint32_t q4 = (r3 * 205) >> 11;
uint32_t r4 = r3 - q4 * 10;
obuf[por + 0] = '0' + q3;
obuf[por + 1] = '0' + q4;
obuf[por + 2] = '0' + r4;
memcpy(obuf + por + 3, pre.num + (n4 << 2), 4);
memcpy(obuf + por + 7, pre.num + (n3 << 2), 4);
memcpy(obuf + por + 11, pre.num + (n2 << 2), 4);
memcpy(obuf + por + 15, pre.num + (n1 << 2), 4);
por += 19;
} else if (x >= 100000000000000000) {
uint32_t q3 = (q2 * 205) >> 11;
uint32_t r3 = q2 - q3 * 10;
obuf[por + 0] = '0' + q3;
obuf[por + 1] = '0' + r3;
memcpy(obuf + por + 2, pre.num + (n4 << 2), 4);
memcpy(obuf + por + 6, pre.num + (n3 << 2), 4);
memcpy(obuf + por + 10, pre.num + (n2 << 2), 4);
memcpy(obuf + por + 14, pre.num + (n1 << 2), 4);
por += 18;
} else {
obuf[por + 0] = '0' + q2;
memcpy(obuf + por + 1, pre.num + (n4 << 2), 4);
memcpy(obuf + por + 5, pre.num + (n3 << 2), 4);
memcpy(obuf + por + 9, pre.num + (n2 << 2), 4);
memcpy(obuf + por + 13, pre.num + (n1 << 2), 4);
por += 17;
}
} else {
int i = 8;
char buf[12];
while (x >= 10000) {
memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
x /= 10000;
i -= 4;
}
if (x < 100) {
if (x < 10) {
write(char('0' + x));
} else {
obuf[por + 0] = '0' + x / 10;
obuf[por + 1] = '0' + x % 10;
por += 2;
}
} else {
if (x < 1000) {
memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
por += 3;
} else {
memcpy(obuf + por, pre.num + (x << 2), 4);
por += 4;
}
}
memcpy(obuf + por, buf + i + 4, 8 - i);
por += 8 - i;
}
}
inline int getChar() {
if (pil + 32 > pir) load();
return ibuf[pil++]; }
inline int readChar() {
if (pil + 32 > pir) load();
int c = getChar();
while (c != -1 && c <= 32) c = getChar();
return c;
}
inline void read(char *s) {
int c = readChar();
while (c > 32)
*s++ = c, c = getChar();
*s = 0;
}
inline void read(std::string &s) {
s.clear();
int c = readChar();
while (c > 32) s.push_back(c), c = getChar();
}
inline void write(const char *s) {
while (*s) {
if (por + 32 > SZ) flush();
write(*s++);
}
}
inline void write(std::string &s) {
for (auto &i: s) {
if (por + 32 > SZ) flush();
write(i);
}
}
inline void write(double x) {
if (por + 32 > SZ) flush();
if (x < 0)
write('-'), x = -x;
int t = (int) x;
write(t), x -= t;
write('.');
for (int i = 18 - 1; i > 0; i--) {
x *= 10;
t = std::min(9, (int) x);
write('0' + t), x -= t;
}
x *= 10;
t = std::min(9, (int) (x + 0.5));
write('0' + t);
}
template<typename T, typename ...Args>
inline void read(T &x, Args &...args) {
read(x);
read(args...);
}
template<typename T, typename ...Args>
inline void write(T x, Args ...args) {
write(x);
write(args...);
}
struct AutoFlush {
~AutoFlush() { flush(); }
} AutoFlush;
} // namespace fastio
using fastio::read;
using fastio::write;
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;
read(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;
read(a1[i].x);
a1[i].y = 1;
}
for (int i = 0; i < w; i++) {
// cin >> b1[i].x;
read(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().y <= (a.back().x - ff.x) * ff.y) {
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().y <= (b.back().x - ff.x) * ff.y) {
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(2, vector<ll>(w + 1, INT64_MAX));
dp[0][0] = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w + 1; j++) {
dp[1][j] = INT64_MAX;
}
for (int j = 0; j < w; j++) {
dp[1][j] = min(dp[1][j], dp[0][j] + b[j].x * a[i].y);
dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + a[i].x * b[j].y);
}
swap(dp[0], dp[1]);
}
ans += dp[1][w - 1];
// cout << dp[0][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().y <= (a.back().x - ff.x) * ff.y) {
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().y <= (b.back().x - ff.x) * ff.y) {
b.push_back(ff);
break;
} else {
b.back().y += ff.y;
}
}
b.push_back(bs[i]);
}
h = a.size();
w = b.size();
for (int i = 0; i < 2; 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 + 1; j++) {
dp[1][j] = INT64_MAX;
}
for (int j = 0; j < w; j++) {
dp[1][j] = min(dp[1][j], dp[0][j] + b[j].x * a[i].y);
dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + a[i].x * b[j].y);
}
swap(dp[0], dp[1]);
}
ans += dp[1][w - 1];
// cout << dp[0][w - 1] << '\n';
// cout << ans << '\n';
write(ans, '\n');
}
Compilation message
kyoto.cpp: In function 'void solve()':
kyoto.cpp:327: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]
327 | for (int i = 0; i < as.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:330: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]
330 | for (int i = 0; i < bs.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:359: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]
359 | for (int i = 0; i < af.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:374: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]
374 | for (int i = 0; i < bf.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:404: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]
404 | for (int i = 0; i < as.size(); i++) {
| ~~^~~~~~~~~~~
kyoto.cpp:419: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]
419 | for (int i = 0; i < bs.size(); i++) {
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
2 ms |
1884 KB |
Output is correct |
5 |
Correct |
2 ms |
1880 KB |
Output is correct |
6 |
Correct |
1 ms |
1116 KB |
Output is correct |
7 |
Correct |
5 ms |
3676 KB |
Output is correct |
8 |
Correct |
5 ms |
3676 KB |
Output is correct |
9 |
Correct |
5 ms |
3676 KB |
Output is correct |
10 |
Correct |
5 ms |
3756 KB |
Output is correct |
11 |
Correct |
7 ms |
3772 KB |
Output is correct |
12 |
Correct |
6 ms |
3676 KB |
Output is correct |
13 |
Correct |
5 ms |
3676 KB |
Output is correct |
14 |
Correct |
5 ms |
3748 KB |
Output is correct |
15 |
Correct |
4 ms |
3676 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
604 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
604 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
344 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
0 ms |
348 KB |
Output is correct |
29 |
Correct |
0 ms |
348 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
2 ms |
1884 KB |
Output is correct |
33 |
Correct |
2 ms |
1880 KB |
Output is correct |
34 |
Correct |
1 ms |
1116 KB |
Output is correct |
35 |
Correct |
5 ms |
3676 KB |
Output is correct |
36 |
Correct |
5 ms |
3676 KB |
Output is correct |
37 |
Correct |
5 ms |
3676 KB |
Output is correct |
38 |
Correct |
5 ms |
3756 KB |
Output is correct |
39 |
Correct |
7 ms |
3772 KB |
Output is correct |
40 |
Correct |
6 ms |
3676 KB |
Output is correct |
41 |
Correct |
5 ms |
3676 KB |
Output is correct |
42 |
Correct |
5 ms |
3748 KB |
Output is correct |
43 |
Correct |
4 ms |
3676 KB |
Output is correct |
44 |
Correct |
1 ms |
348 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
1 ms |
344 KB |
Output is correct |
47 |
Correct |
0 ms |
348 KB |
Output is correct |
48 |
Correct |
0 ms |
348 KB |
Output is correct |
49 |
Correct |
0 ms |
344 KB |
Output is correct |
50 |
Correct |
1 ms |
348 KB |
Output is correct |
51 |
Correct |
0 ms |
348 KB |
Output is correct |
52 |
Correct |
0 ms |
348 KB |
Output is correct |
53 |
Correct |
1 ms |
344 KB |
Output is correct |
54 |
Correct |
1 ms |
348 KB |
Output is correct |
55 |
Correct |
3 ms |
1880 KB |
Output is correct |
56 |
Correct |
0 ms |
348 KB |
Output is correct |
57 |
Correct |
1 ms |
604 KB |
Output is correct |
58 |
Correct |
1 ms |
860 KB |
Output is correct |
59 |
Correct |
7 ms |
3676 KB |
Output is correct |
60 |
Correct |
7 ms |
3676 KB |
Output is correct |
61 |
Correct |
7 ms |
3676 KB |
Output is correct |
62 |
Correct |
7 ms |
3676 KB |
Output is correct |
63 |
Execution timed out |
2095 ms |
12008 KB |
Time limit exceeded |
64 |
Halted |
0 ms |
0 KB |
- |