QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140338#4561. Catfish Farmpandapythoner#3 153ms48556kbC++174.9kb2023-08-15 18:48:312024-07-04 01:44:14

Judging History

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

  • [2024-07-04 01:44:14]
  • 评测
  • 测评结果:3
  • 用时:153ms
  • 内存:48556kb
  • [2023-08-15 18:48:31]
  • 提交

answer

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else

#endif

#include <bits/stdc++.h>

#include "fish.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

const ll inf = 1e18;
mt19937 rnd(234);

int n, m;
vector<int> w;
vector<pair<int, int>> poss;
vector<vector<pair<ll, ll>>> bbr_cst;
vector<vector<ll>> bbr;

ll solve() {
    bbr.assign(n, vector<ll>());
    bbr_cst.assign(n, vector<pair<ll, ll>>());
    for (int i = 0; i < m; i += 1) {
        auto [x, y] = poss[i];
        bbr[x].push_back(y);
        bbr_cst[x].push_back(make_pair(y, w[i]));
    }
    for (int x = 0; x < n; x += 1) {
        sort(all(bbr[x]));
        sort(all(bbr_cst[x]));
    }
    auto get_bbr = [&](int i) -> vector<ll> {
        if (i < 0 || i >= n) {
            return {};
        }
        return bbr[i];
    };
    auto uniq = [&](vector<ll> &a) -> void {
        a.resize(unique(all(a)) - a.begin());
    };
    auto uniq_ret = [&](vector<ll> a) -> vector<ll> {
        uniq(a);
        return a;
    };
    auto mrg = [&](const vector<ll> &a, const vector<ll> &b) -> vector<ll> {
        int asz = (int)a.size();
        int bsz = (int)b.size();
        vector<ll> c(asz + bsz);
        merge(all(a), all(b), c.begin());
        return c;
    };
    auto get_idx = [&](const vector<ll> &a, ll x) -> int {
        auto it = lower_bound(all(a), x);
        if (it == a.end() || *it != x) {
            return -1;
        }
        return it - a.begin();
    };
    auto get_summ_on_seg = [&](const vector<ll> &vct, const vector<ll> &psms, ll xl, ll xr) -> ll {
        if (xl > xr) {
            return 0;
        }
        int l = lower_bound(all(vct), xl) - vct.begin();
        int r = upper_bound(all(vct), xr) - vct.begin();
        return psms[r] - psms[l];
    };
    vector dp(n + 1, vector(2, vector<ll>()));
    dp[0][0] = {0, -inf};
    dp[0][1] = {-inf, -inf};
    for (int i = 0; i < n; i += 1) {
        auto prev_prev_vct = uniq_ret(mrg({0, inf}, get_bbr(i - 2)));
        auto prev_vct = uniq_ret(mrg({0, inf}, get_bbr(i - 1)));
        auto my_vct = uniq_ret(mrg({0, inf}, get_bbr(i)));
        int prev_prev_sz = (int)prev_prev_vct.size();
        int prev_sz = (int)prev_vct.size();
        int my_sz = (int)(my_vct.size());
        vector<ll> prev_psms(prev_sz + 1, 0), my_psms(my_sz + 1, 0);
        if (i > 0) {
            for (auto [y, cst] : bbr_cst[i - 1]) {
                prev_psms[get_idx(prev_vct, y) + 1] += cst;
            }
        }
        for (auto [y, cst] : bbr_cst[i]) {
            my_psms[get_idx(my_vct, y) + 1] += cst;
        }
        for (int i = 1; i <= prev_sz; i += 1) {
            prev_psms[i] += prev_psms[i - 1];
        }
        for (int i = 1; i <= my_sz; i += 1) {
            my_psms[i] += my_psms[i - 1];
        }
        dp[i + 1][0].assign(my_sz, -inf);
        dp[i + 1][1].assign(my_sz, -inf);
        int k = 0;
        ll opt_k_sm = -inf;
        for (int j = 0; j < my_sz; j += 1) {
            ll y = my_vct[j];
            while (k < prev_sz && prev_vct[k] < y) {
                if (opt_k_sm < dp[i][0][k]) {
                    opt_k_sm = dp[i][0][k];
                }
                opt_k_sm += prev_psms[k + 1] - prev_psms[k];
                k += 1;
            }
            dp[i + 1][0][j] = max(dp[i + 1][0][j], opt_k_sm);
        }
        if (i > 0) {
            for (int j = 0; j < my_sz; j += 1) {
                ll y = my_vct[j];
                for (int k = 0; k < prev_prev_sz; k += 1) {
                    ll py = prev_prev_vct[k];
                    dp[i + 1][0][j] = max(dp[i + 1][0][j], max(dp[i - 1][1][k], dp[i - 1][0][k]) + get_summ_on_seg(prev_vct, prev_psms, 0, max(y, py) - 1));
                }
            }
        }
        opt_k_sm = -inf;
        k = prev_sz - 1;
        for (int j = my_sz - 1; j >= 0; j -= 1) {
            ll y = my_vct[j];
            while (k >= 0 && prev_vct[k] > y) {
                if (opt_k_sm < dp[i][1][k]) {
                    opt_k_sm = dp[i][1][k];
                }
                k -= 1;
            }
            opt_k_sm += my_psms[j + 1] - my_psms[j];
			while (k >= 0 && prev_vct[k] >= y) {
                if (opt_k_sm < dp[i][1][k]) {
                    opt_k_sm = dp[i][1][k];
                }
                k -= 1;
            }
            dp[i + 1][1][j] = max(dp[i + 1][1][j], opt_k_sm);
        }
    }
    ll rs = -inf;
    for (auto x : dp[n][0]) {
        rs = max(rs, x);
    }
    for (auto x : dp[n][1]) {
        rs = max(rs, x);
    }
    return rs;
}

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    n = N;
    m = M;
    poss.resize(m);
    w = W;
    for (int i = 0; i < m; i += 1) {
        poss[i] = make_pair(X[i], Y[i]);
    }
    ll rs = solve();
    return rs;
}

詳細信息

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 56ms
memory: 26932kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
90000 80699
0 10792 55091480
0 36762 389250726
0 79267 706445371
0 76952 290301137
0 13444 69711795
0 68980 66221400
0 1695 703252611
0 36628 632571604
0 87676 264578012
0 79496 397448339
0 57929 447544332
0 35453 355374818
0 62449 686423696
0 45614 667165709...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
40313272768926

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 71ms
memory: 30068kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 100000
0 64777 995289349
0 71596 893436841
0 577 789941184
0 74238 421759180
0 93045 833843112
0 17349 236016162
0 70194 646518626
0 59769 662584325
0 45550 706340730
0 8007 454213805
0 5460 328535742
0 47262 672607739
0 91960 166922115
0 26216 5441740...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
49915093555295

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 26ms
memory: 22628kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 1
0 0 10082010

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
10082010

result:

ok 3 lines

Test #4:

score: 0
Accepted
time: 29ms
memory: 22684kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 1
0 99999 19122012

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
19122012

result:

ok 3 lines

Test #5:

score: 0
Accepted
time: 153ms
memory: 46124kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 300000
94880 38243 268662731
31482 11260 116303310
31482 29385 147398833
85804 78816 165663896
85804 50892 232441179
85804 52149 500231552
31482 15077 912836767
94880 13332 204098181
85804 4048 862989578
31482 94135 432330909
85804 30398 552396632
3702...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
149814460735479

result:

ok 3 lines

Test #6:

score: 0
Accepted
time: 152ms
memory: 48556kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 300000
66138 12864 1000000000
3750 4109 1000000000
42566 70555 1000000000
33020 72709 1000000000
57804 39219 1000000000
28208 65932 1000000000
13384 22179 1000000000
69976 69860 1000000000
82704 18635 1000000000
74094 31581 1000000000
95460 25871 10000...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
300000000000000

result:

ok 3 lines

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 6
Accepted
time: 0ms
memory: 4072kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
3 2
0 0 1
1 1 1

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
2

result:

ok 3 lines

Test #8:

score: 0
Accepted
time: 103ms
memory: 32944kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
90000 161862
0 56823 293232472
0 28967 124369573
1 8799 138712011
0 87115 743135614
1 56429 262092699
0 61318 597172732
0 39127 477101342
1 44938 277680401
1 79037 997527330
1 88113 13289754
0 29715 35249311
0 50637 709319782
1 20760 845594381
1 80662 6299890...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
40604614618209

result:

ok 3 lines

Test #9:

score: 0
Accepted
time: 126ms
memory: 37696kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 200000
1 94611 359691437
1 10475 699903763
0 39627 186380865
0 62696 78236869
1 59901 907339766
1 44433 317152581
1 19456 223720937
0 4711 30286661
1 55383 479944093
1 88731 45441550
0 10309 218389901
0 99887 732998760
0 26228 839617653
1 88110 3139856...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
50032678213482

result:

ok 3 lines

Test #10:

score: -6
Wrong Answer
time: 0ms
memory: 3872kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
2 2
0 0 2022
1 1 4044

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
2022

result:

wrong answer 3rd lines differ - expected: '4044', found: '2022'

Subtask #3:

score: 0
Wrong Answer

Test #20:

score: 9
Accepted
time: 25ms
memory: 22620kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 1
0 0 10082010

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
10082010

result:

ok 3 lines

Test #21:

score: -9
Wrong Answer
time: 32ms
memory: 22708kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 1
99999 0 882019

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
0

result:

wrong answer 3rd lines differ - expected: '882019', found: '0'

Subtask #4:

score: 0
Wrong Answer

Test #28:

score: 14
Accepted
time: 0ms
memory: 3816kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
4 3
2 2 1
0 0 1
1 1 1

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
3

result:

ok 3 lines

Test #29:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
8 7
5 5 1
4 4 1
6 6 1
3 3 1
0 0 1
2 2 1
1 1 1

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
7

result:

ok 3 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 4040kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
3 2
0 0 1
1 1 1

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
2

result:

ok 3 lines

Test #31:

score: -14
Wrong Answer
time: 0ms
memory: 3788kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
3 2
2 0 1
1 1 1

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
1

result:

wrong answer 3rd lines differ - expected: '2', found: '1'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Wrong Answer

Test #60:

score: 14
Accepted
time: 70ms
memory: 32384kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
100000 99999
31026 31026 1
42940 42940 1
69303 69303 1
90350 90350 1
77507 77507 1
87126 87126 1
17988 17988 1
5146 5146 1
63023 63023 1
27776 27776 1
6136 6136 1
82557 82557 1
24904 24904 1
21667 21667 1
67271 67271 1
80294 80294 1
81145 81145 1
47144 47144 ...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
99999

result:

ok 3 lines

Test #61:

score: -14
Wrong Answer
time: 39ms
memory: 20336kb

input:

f785163bfcb92ce6ac387bba5d2f29a0e0f37f19
50000 100000
43737 0 616909786
28149 1 83561192
31215 0 81425452
11831 1 127789871
33975 1 294422160
44409 1 920754334
44149 1 547214118
23078 0 749134931
39070 1 425147230
39398 1 49764337
49388 0 1922565
13827 0 24394607
45462 0 276157952
30584 0 435992379
...

output:

938f2698235a9ff1d1d91e23381b68bec7bed102
OK
36292446579575

result:

wrong answer 3rd lines differ - expected: '36454348383152', found: '36292446579575'

Subtask #8:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%