Submission #4026705

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <chrono>
#include <ctime>
#include <bitset>
#include <iterator>
#include <cmath>
#include <stack>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define P pair<long long, long long>
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const double PI = acos(-1.0);

// use unordered_map to save memory usage
unordered_map<int, int> mp;
int get(int x) {
  int ret = mp[x];
  if (ret == 0) {
    mp.erase(x);
    ret = INT_MAX/2;
  }
  return ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int w, h; cin >> w >> h;
  vector<ll> p(w);
  rep(i, w) {
    cin >> p[i];
  }
  vector<ll> q(h);
  rep(i, h) {
    cin >> q[i];
  }
  sort(p.begin(), p.end());
  sort(q.begin(), q.end());
  
  vector<ll> sump(w+1);
  vector<ll> sumq(h+1);
  rep(i, w) {
    sump[i+1] = sump[i] + p[i];
  }
  rep(i, h) {
    sumq[i+1] = sumq[i] + q[i];
  }

  int pos = 0;
  ll ans = sump[w] + sumq[h];
  rep(i, w) {
    while (pos < h && p[i] > q[pos]) {
      pos++;
    }
    ans += sumq[pos] + p[i]*(h-pos);
  }

  cout << ans << endl;
  /*

  _  _  _
  2  2  2
  __3__5_
     7
  __3__5_

  */

}

Submission Info

Judge Result