Guest User

Untitled

a guest
Oct 26th, 2022
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.18 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. // #pragma GCC optimize("O3")
  4. // #include <atcoder/fenwicktree>
  5. using namespace std;
  6.  
  7. #define int long long
  8. using ll = long long;
  9. #define all(x) x.begin(), x.end()
  10. #define rall(x) x.rbegin(), x.rend()
  11. #define rep(i, n) for (int i = 0; i < n; ++i)
  12. #define rep1(i, n) for (int i = 1; i <= n; ++i)
  13. #define repp(i, s, n) for (int i = s; i < n; ++i)
  14.  
  15. #define re(i, n) for (i = 0; i < n; ++i)
  16. int rd() {
  17.     int i;
  18.     cin >> i;
  19.     return i;
  20. }
  21. void solve() {
  22.     int n = rd();
  23.     vector<int> packages(n);
  24.     rep(i, n) cin >> packages[i];
  25.     int m = rd();
  26.     vector<vector<int>> boxes(m);
  27.     rep(i, m) {
  28.         boxes[i].resize(rd());
  29.         for (int &j : boxes[i]) j = rd();
  30.     }
  31.     sort(packages.begin(), packages.end());
  32.     long long res = 1e18;
  33.     long long sum = accumulate(packages.begin(), packages.end(), 0LL);
  34.     bool ok = 0;
  35.     for (int i = 0; i < boxes.size(); i++) {
  36.         sort(boxes[i].begin(), boxes[i].end());
  37.         if (boxes[i][boxes[i].size() - 1] < packages[packages.size() - 1]) {
  38.             continue;
  39.         }
  40.         ok = 1;
  41.         long long ans = 0;
  42.         long long prev = 0;
  43.         for (int p : boxes[i]) {
  44.             long long t = upper_bound(packages.begin(), packages.end(), p) - packages.begin();
  45.             ans += p * (t - prev);
  46.             prev = t;
  47.         }
  48.         res = min(res, ans - sum);
  49.     }
  50.     if (!ok) cout << "-1\n";
  51.     else cout << res;
  52. }
  53.  
  54. signed main() {
  55.     // #ifndef DEBUG
  56.     //     freopen("ugly.in", "r", stdin);
  57.     //     freopen("ugly.out", "w", stdout);
  58.     // #endif
  59.  
  60.     // auto start = chrono::steady_clock::now();
  61.  
  62.     cin.tie(0)->sync_with_stdio(false);
  63.  
  64.     int tc = 1;
  65.     cout << fixed << setprecision(10);
  66.     // cin >> tc;
  67.     //
  68.     for (int i = 1; i <= tc; ++i) {
  69.         // cerr << i << endl;
  70.         // cout << "Case #" << i << ": ";
  71.         // cerr << "case " << i << ":\n";
  72.         solve();
  73.         // cerr << endl;
  74.     }
  75.  
  76.     // cerr << "final: "
  77.     //      << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() -
  78.     //      start).count()
  79.     //      << "ms";
  80. }
Advertisement
Add Comment
Please, Sign In to add comment