QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46042#4412. Boss RushmiaomiaoziWA 1296ms16740kbC++172.5kb2022-08-24 22:34:242022-08-24 22:34:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-24 22:34:25]
  • 评测
  • 测评结果:WA
  • 用时:1296ms
  • 内存:16740kb
  • [2022-08-24 22:34:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// https://space.bilibili.com/672346917

#ifndef LOCAL
#define LOG(...) 42
#endif

#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long LL;
typedef pair <int, int> PII;

constexpr LL inf = 1e18;
constexpr double EPS = 1e-8;
const double PI = acos(-1);

int multi_cases = 1;

void A_SOUL_AvA () {
    int n;
    LL H;
    cin >> n >> H;
    vector d(n, vector<LL>(1));
    vector t(n, 0), len(n, 0);
    for (int i = 0; i < n; i++) {
        int m;
        cin >> t[i] >> m;
        len[i] = m;
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            d[i].pb(x);
        }
        for (int j = 1; j < (int)d[i].size(); j++) {
            d[i][j] += d[i][j - 1];
        }
    }

    LL ans = inf;
    vector <LL> f(1 << n, inf);

    for (int S = (1 << n) - 1; S >= 1; S--) {
        vector <pair<int, int>> used;
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (S >> i & 1) {
                used.pb({last, i});
                last += t[i];
            }
        }

        int l = 0, r = 0;
        vector <int> st(n, -1);
        for (auto &[sta, idx] : used) {
            r = max(r, sta + t[idx]);
            st[idx] = sta;
        }
        r += 5;

        auto chk = [&](int mid) -> int {
            LL now = 0;

            for (int i = 0; i < n; i++) if (st[i] != -1) {
                int sta = st[i];
                if (mid < sta) continue;
                if (sta + len[i] - 1 <= mid) {
                    now += d[i].back();
                } else {
                    // mid >= sta && sta + len[i] - 1 > mid
                    int diff = mid - sta + 1;
                    now += d[i][diff];
                }
            }
            return now >= H;
        };
        
        
        while (l < r) {
            int mid = l + r >> 1;

            if (chk(mid)) r = mid;
            else l = mid + 1;
        }

        if (chk(r)) {
            ans = min(ans, 1LL * r);
            // LOG(ans, used);
        }
    }

    cout << (ans == inf ? -1 : ans) << endl;
}

int main () {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int T = 1;
    for (multi_cases && cin >> T; T; T--) {
        A_SOUL_AvA ();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1296ms
memory: 16740kb

input:

100
10 293367178351
89 52
117480172 951737726 356435682 180765874 775623083 281703307 290364363 366421773 989361116 796791408 389709469 534380525 412173405 463001602 578985383 272777986 833157533 444367936 841474617 472532665 952319800 583679381 924952511 892974994 105808118 171375863 320943603 4870...

output:

418
625
643
268
429
407
307
721
334
597
544
594
477
557
392
-1
412
471
533
188
255
-1
362
249
361
243
75
190
450
297
251
372
378
-1
-1
281
145
183
334
158
448
313
149
218
369
190
282
270
186
330
527
173
619
415
434
-1
215
342
300
452
285
569
369
392
542
480
307
535
360
550
130
289
370
498
232
144
14...

result:

wrong answer 1st lines differ - expected: '368', found: '418'