#include<bits/stdc++.h> using namespace std; // define //bool M1; //#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n"; //#define memory cerr << abs(&M2 - &M1)/1024.0/1024 << " MB" << "\n" #define ll long long #define ii pair <ll , ll> #define iii pair <int , ii> #define se second #define fi first #define all(v) (v).begin() , (v).end() #define Unique(v) sort(all(v)) , v.resize(unique(all(v)) - v.begin()) #define bit(x,i) (((x) >> (i)) & 1LL) #define flip(x,i) ((x) ^ (1LL << (i))) #define ms(d,x) memset(d , x , sizeof(d)) #define exist __exist #define ends __ends #define visit visited #define left __left #define right __right #define prev __prev #define next __next #define sitingfake 1 #define orz 1 //constant const long long mod = 1e9 + 7; const long long linf = 4557430888798830399LL; const long long nlinf = -4485090715960753727LL; const int inf = 1061109567; const int ninf = -1044266559; const int dx[] = {0 , -1 , 0 , 1}; const int dy[] = {-1 , 0 , 1 , 0}; template<typename T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } template<typename T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } void Plus(ll & a ,ll b) { b %= mod; a += b; if(a < 0) a += mod; a %= mod; return; } void Mul(ll & a, ll b) { (a *= (b % mod)) %= mod; return; } //code const int maxn = 1e5 + 7; int a[maxn] , b[maxn]; int n , m; namespace sub1 { ll dp[1002][1002]; void solve() { ms(dp , 0x3f); dp[1][1] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(ii(i , j) == ii(1 , 1)) continue; dp[i][j] = linf; if(i) dp[i][j] = min(dp[i][j] , dp[i - 1][j] + 1ll * b[j]); if(j) dp[i][j] = min(dp[i][j] , dp[i][j - 1] + 1ll * a[i]); } } cout << dp[n][m]; } } namespace sub2 { ll dp[1005][1005]; bool approve() { for(int i = 1; i <= n; i++) if(a[i] > 1000) return 0; for(int i = 1; i <= m; i++) if(b[i] > 1000) return 0; return 1; } void solve() { vector <int> new_a , new_b; int Min = inf; for(int i = 1; i <= n; i++) { if(minimize(Min , a[i])) new_a.push_back(i); } Min = inf; for(int i = n; i >= 1; i--) { if(minimize(Min , a[i])) new_a.push_back(i); } Min = inf; for(int i = 1; i <= m; i++) { if(minimize(Min , b[i])) new_b.push_back(i); } Min = inf; for(int i = m; i >= 1; i--) { if(minimize(Min , b[i])) new_b.push_back(i); } Unique(new_a); Unique(new_b); n = new_a.size(); m = new_b.size(); ms(dp , 0x3f); dp[1][1] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(ii(i , j) == ii(1 , 1)) continue; dp[i][j] = linf; if(i) dp[i][j] = min(dp[i][j] , dp[i - 1][j] + 1ll * (new_a[i - 1] - new_a[i - 2]) * b[j]); if(j) dp[i][j] = min(dp[i][j] , dp[i][j - 1] + 1ll * (new_b[i - 1] - new_b[i - 2]) * a[i]); } } cout << dp[n][m]; } } namespace sub3 { ll ccw(ii a, ii b , ii c) { return (c.se - a.se) * (b.fi - a.fi) - (c.fi - a.fi) * (b.se - a.se); } bool cmp(ii &a1 , ii &a2 , ii &b1 , ii &b2) { ll d_Xa = a2.fi - a1.fi; ll d_Ya = a2.se - a1.se; ll d_Xb = b2.fi - b1.fi; ll d_Yb = b2.se - b1.se; // ya / xa <= yb / xb return d_Ya * d_Xb <= d_Yb * d_Xa; } void debug(vector <ii> p) { cout << endl; for(ii it : p) cout << it.fi << " " << it.se << endl; cout << endl; } void solve() { vector <ii> HullA , HullB; HullA.push_back({n , a[n]}); HullA.push_back({n - 1 , a[n - 1]}); for(int i = n - 2; i >= 1; i--) { while(HullA.size() >= 2 && ccw(HullA[HullA.size() - 2] , HullA.back() , ii(i , a[i])) >= 0) { HullA.pop_back(); } HullA.push_back({i , a[i]}); } reverse(all(HullA)); HullB.push_back({m , b[m]}); HullB.push_back({m - 1 , b[m - 1]}); for(int i = m - 2; i >= 1; i--) { while(HullB.size() >= 2 && ccw(HullB[HullB.size() - 2] , HullB.back() , ii(i , b[i])) >= 0) { HullB.pop_back(); } HullB.push_back({i , b[i]}); } reverse(all(HullB)); // // debug(HullA); // debug(HullB); int itL = 1 , itR = 1; n = HullA.size(); m = HullB.size(); ll ans = 0; while(itL < n && itR < m) { if(cmp(HullA[itL - 1] , HullA[itL] , HullB[itR - 1] , HullB[itR])) { ans += HullB[itR - 1].se * (HullA[itL].fi - HullA[itL - 1].fi); ++itL; } else { ans += HullA[itL - 1].se * (HullB[itR].fi - HullB[itR - 1].fi); ++itR; } } //cout << itL << " " << itR << " " << ans << endl; for(int i = itL; i < n; i++) { ans += (HullA[i].fi - HullA[i - 1].fi) * HullB[m - 1].se; } for(int i = itR; i < m; i++) { ans += (HullB[i].fi - HullB[i - 1].fi) * HullA[n - 1].se; } cout << ans; } } void solve(void) { cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= m; i++) cin >> b[i]; if(n <= 1000 && m <= 1000) return sub1 :: solve(); if(sub2 :: approve()) return sub2 :: solve(); return sub3 :: solve(); } /** **/ //bool M2; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int tc = 1; // cin >> tc; while(tc--) solve(); // execute; // memory; }

kyoto.cpp: In function 'int main()':
kyoto.cpp:260:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  260 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
kyoto.cpp:261:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  261 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~