Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
- // #pragma GCC optimize("O3")
- // #include <atcoder/fenwicktree>
- using namespace std;
- #define int long long
- using ll = long long;
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define rep(i, n) for (int i = 0; i < n; ++i)
- #define rep1(i, n) for (int i = 1; i <= n; ++i)
- #define repp(i, s, n) for (int i = s; i < n; ++i)
- #define re(i, n) for (i = 0; i < n; ++i)
- int rd() {
- int i;
- cin >> i;
- return i;
- }
- void solve() {
- int n = rd();
- vector<int> packages(n);
- rep(i, n) cin >> packages[i];
- int m = rd();
- vector<vector<int>> boxes(m);
- rep(i, m) {
- boxes[i].resize(rd());
- for (int &j : boxes[i]) j = rd();
- }
- sort(packages.begin(), packages.end());
- long long res = 1e18;
- long long sum = accumulate(packages.begin(), packages.end(), 0LL);
- bool ok = 0;
- for (int i = 0; i < boxes.size(); i++) {
- sort(boxes[i].begin(), boxes[i].end());
- if (boxes[i][boxes[i].size() - 1] < packages[packages.size() - 1]) {
- continue;
- }
- ok = 1;
- long long ans = 0;
- long long prev = 0;
- for (int p : boxes[i]) {
- long long t = upper_bound(packages.begin(), packages.end(), p) - packages.begin();
- ans += p * (t - prev);
- prev = t;
- }
- res = min(res, ans - sum);
- }
- if (!ok) cout << "-1\n";
- else cout << res;
- }
- signed main() {
- // #ifndef DEBUG
- // freopen("ugly.in", "r", stdin);
- // freopen("ugly.out", "w", stdout);
- // #endif
- // auto start = chrono::steady_clock::now();
- cin.tie(0)->sync_with_stdio(false);
- int tc = 1;
- cout << fixed << setprecision(10);
- // cin >> tc;
- //
- for (int i = 1; i <= tc; ++i) {
- // cerr << i << endl;
- // cout << "Case #" << i << ": ";
- // cerr << "case " << i << ":\n";
- solve();
- // cerr << endl;
- }
- // cerr << "final: "
- // << chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() -
- // start).count()
- // << "ms";
- }
Advertisement
Add Comment
Please, Sign In to add comment