| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1321712 | patgra | Sightseeing in Kyoto (JOI22_kyoto) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define int long long
#define ld long double
#define pb push_back
using namespace std;
constexpr int inf = 2e18;
int n, m;
vector<int> a, b;
map<array<int, 4>, int> mp;
int _solve(int la, int ra, int lb, int rb) {
if(la == ra) return a[la] * (rb - lb);
if(lb == rb) return b[lb] * (ra - la);
if(la + 1 == ra) {
int ans = inf;
rep(i, lb, rb + 1) ans = min(ans, a[la] * (i - lb) + b[i] + a[ra] * (rb - i));
return ans;
}
if(lb + 1 == rb) {
int ans = inf;
rep(i, la, ra + 1) ans = min(ans, b[lb] * (i - la) + a[i] + b[rb] * (ra - i));
return ans;
}
pair<int, int> mn = {inf, -1};
rep(i, la + 1, ra) mn = min(mn, {a[i], i});
int ma = mn.second;
mn = {inf, -1};
rep(i, lb + 1, rb) mn = min(mn, {b[i], i});
int mb = mn.second;
auto ans = min({a[la] * (rb - lb) + b[rb] * (ra - la), b[lb] * (ra - la) + a[ra] * (rb - lb), solve(la, ma, lb, mb) + solve(ma, ra, mb, rb)});
ans = min(ans, a[la] * (mb - lb) + solve(la, ra, mb, rb));
ans = min(ans, b[lb] * (ma - la) + solve(ma, ra, lb, rb));
ans = min(ans, a[ra] * (rb - mb) + solve(la, ra, lb, mb));
ans = min(ans, b[rb] * (ra - ma) + solve(la, ma, lb, rb));
return ans;
}
int solve(int la, int ra, int lb, int rb) {
array<int, 4> ar = {la, ra, lb, rb};
if(!mp.count(ar)) mp[ar] = _solve(la, ra, lb, rb);
return mp[ar];
}
void bru() {
vector<vector<array<int, 3>>> dp(n, vector<array<int, 3>>(m, {inf, -1, -1}));
dp[0][0] = {0, 0, 0};
rep(i, 0, n) rep(j, 0, m) {
auto x = dp[i][j][0];
if(i < n - 1) dp[i + 1][j] = min(dp[i + 1][j], {x + b[j], i, j});
if(j < m - 1) dp[i][j + 1] = min(dp[i][j + 1], {x + a[i], i, j});
}
stack<array<int, 3>> s;
int x = n - 1, y = m - 1;
while(x || y) {
auto [d, nx, ny] = dp[x][y];
s.push({d - dp[nx][ny][0], x, y});
x = nx, y = ny;
}
cout << dp[n - 1][m - 1][0] << '\n';
DC << "0, 0\n";
while(s.size()) {
auto [c, x, y] = s.top(); s.pop();
DC << " -> " << x << ", " << y << " \tcosting " << c << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
a.resize(n), b.resize(m);
repIn(i, a) cin >> i;
repIn(i, b) cin >> i;
cout << solve(0, n - 1, 0, m - 1) << '\n';
//bru();
}