QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#122888#1808. Efficient PartitioningScarlett_boyTL 4ms7204kbC++173.6kb2023-07-11 13:42:592023-07-11 13:43:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-11 13:43:02]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:7204kb
  • [2023-07-11 13:42:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6 + 10;

int n;
#define int long long

const ll Eps = 1e17, L = 1, R = 1e18;

struct Tree {
#define LOG 65
    int root, cnt;
    ll Mi, Ma;
    vector<int> ls, rs;
    vector<ll> MAX1, MAX2;

    Tree(int M = 0, ll Min = 1, ll Max = 2e18) : ls(M * LOG), rs(M * LOG), MAX1(M * LOG), MAX2(M * LOG) {
        root = 0, cnt = 0;
        Mi = Min, Ma = Max;
    }

    inline void pushup(int p) {
        MAX1[p] = max(MAX1[ls[p]], MAX1[rs[p]]);
        MAX2[p] = max(MAX2[ls[p]], MAX2[rs[p]]);
    }

    inline void New(int &p) {
        p = ++cnt;
        MAX1[p] = MAX2[p] = -Eps;
    }

    inline void update(int &p, ll l, ll r, ll x, ll w1, ll w2) {
        if (!p) New(p);
        if (l == r) {
            MAX1[p] = max(MAX1[p], w1);
            MAX2[p] = max(MAX2[p], w2);
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) update(ls[p], l, mid, x, w1, w2);
        else update(rs[p], mid + 1, r, x, w1, w2);
        pushup(p);
    }

    inline void update(int x, ll w1, ll w2) { update(root, Mi, Ma, x, w1, w2); }

    inline ll query1(int p, ll l, ll r, ll x, ll y) {
        if (!p) return -Eps;
        if (x <= l && r <= y) return MAX1[p];
        ll ans = -Eps;
        int mid = l + r >> 1;
        if (x <= mid) ans = max(ans, query1(ls[p], l, mid, x, y));
        if (y > mid) ans = max(ans, query1(rs[p], mid + 1, r, x, y));
        return ans;
    }

    inline ll query1(ll l, ll r) { return query1(root, Mi, Ma, l, r); }

    inline ll query2(int p, ll l, ll r, ll x, ll y) {
        if (!p) return -Eps;
        if (x <= l && r <= y) return MAX2[p];
        ll ans = -Eps;
        int mid = l + r >> 1;
        if (x <= mid) ans = max(ans, query2(ls[p], l, mid, x, y));
        if (y > mid) ans = max(ans, query2(rs[p], mid + 1, r, x, y));
        return ans;
    }

    inline ll query2(ll l, ll r) { return query2(root, Mi, Ma, l, r); }
};


void solve() {
    cin >> n;
    vector<ll> a(n + 5), b(n + 5), c(n + 5), sum(n + 5);
    vector<ll> dp(n + 5, -Eps);
    Tree T(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    sum[0] = a[0];
    for (int i = 1; i < n; i++) sum[i] = a[i] + sum[i - 1];

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            dp[i] = a[i] + b[i] + c[i];
        } else {
            for (int j = 0; j < i; j++) {
                dp[i] = max(dp[i], min(dp[j], b[j + 1] + c[i] + sum[i] - sum[j]));
            }
            dp[i] = max(dp[i], b[0] + c[i] + sum[i]);
        }
//            T.update(dp[i] - b[i + 1] + sum[i] + Eps, dp[i], b[i + 1] - sum[i]);
//        } else {
//            ll x = c[i] + sum[i] + Eps;
//            dp[i] = max(T.query1(L, x), T.query2(x, R) + c[i] + sum[i]);
//            if (i != n - 1)T.update(dp[i] - b[i + 1] + sum[i] + Eps, dp[i], b[i + 1] - sum[i]);
//        }
    }
    cout << dp[n - 1] << '\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _ = 1;
//    cin >> _;
    for (int o = 1; o <= _; o++) {
        //      cout << "Case #<<" << o << ": ";
        solve();
    }
    return 0;
}

/*


11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -728713779 573207953 115652694 -686953578 -215986240

91174984

*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3452kb

input:

2
1 -1
-1 4
1 -2

output:

1

result:

ok answer is '1'

Test #2:

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

input:

1
1000000000
1000000000
1000000000

output:

3000000000

result:

ok answer is '3000000000'

Test #3:

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

input:

11
-323225375 -897098227 -795978453 501188072 409939326 -362890219 969123048 962633819 252457646 694824070 -406990840
-696821643 -663750226 -570551722 670541392 172964990 399404695 -305728788 -157617655 -801518744 -328729631 -160335217
-465411342 -660775657 515997870 -34787742 628368976 84800619 -72...

output:

91174984

result:

ok answer is '91174984'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

2
12 3
-13 -1
-19 7

output:

9

result:

ok answer is '9'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

9
-13 -10 18 4 -9 8 -12 18 1
3 3 7 10 -16 -10 8 -7 -19
-20 15 -17 2 7 15 11 14 8

output:

16

result:

ok answer is '16'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

10
-3 -20 -13 19 -12 2 -15 -9 -12 -15
8 20 8 19 9 -13 8 16 10 8
12 8 7 14 -1 -11 -7 -6 4 -7

output:

-14

result:

ok answer is '-14'

Test #7:

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

input:

2
-17 -12
-4 15
1 -13

output:

-20

result:

ok answer is '-20'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

6
2 -7 18 -14 9 -3
16 1 19 18 20 9
19 5 -11 -15 -18 2

output:

23

result:

ok answer is '23'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

304
765 910 -240 338 -689 892 -518 663 447 796 716 -830 -465 835 426 88 -49 -810 -159 326 -345 -925 97 -371 496 921 693 526 785 -218 -939 119 935 -994 510 716 513 -18 -202 943 107 654 -940 629 592 529 618 403 -497 -538 -996 496 -499 80 768 714 -346 -477 883 -527 -116 -362 -462 389 818 -470 -124 -523...

output:

26103

result:

ok answer is '26103'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

383
551 205 -487 863 524 352 490 -44 -641 385 338 -915 -937 -588 -745 785 -574 -699 280 877 848 -418 -443 577 350 121 -420 -539 531 73 578 -836 238 -62 -792 -444 -558 -174 964 -531 3 -1000 -878 -879 -350 349 -957 345 -577 938 -865 -830 -574 760 496 58 697 868 830 372 -695 357 -582 423 -19 -536 -962 ...

output:

68

result:

ok answer is '68'

Test #11:

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

input:

293
-355 -542 -948 207 341 300 -15 48 170 -525 869 693 604 273 208 91 -130 846 -270 -621 470 831 -766 -997 -271 652 560 -411 -479 -790 -974 -4 -186 -565 -874 -653 993 -228 886 -189 982 -130 15 -644 282 432 658 264 441 297 -364 -19 170 -624 596 -184 -9 -426 -403 216 430 -168 -366 245 -755 -667 301 16...

output:

-483

result:

ok answer is '-483'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

211
22 858 192 -191 885 -30 310 931 -996 553 323 -551 524 770 158 406 -374 -136 -575 768 -873 772 10 -370 -830 674 697 -734 115 -183 609 -471 -172 875 219 574 352 -880 922 58 -129 349 -90 368 -154 701 715 711 -374 -102 970 -338 411 -286 -988 -470 4 83 -780 -595 831 -951 666 701 -215 -302 -380 643 -3...

output:

15031

result:

ok answer is '15031'

Test #13:

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

input:

203
43 665 -647 -672 395 614 774 758 -906 -117 695 372 -350 -613 -462 -820 -983 313 807 -926 -728 986 557 800 550 725 777 -692 -89 179 -239 286 620 254 241 956 -278 -152 200 700 -145 -596 -812 206 367 62 866 -237 382 -872 -783 461 299 541 474 429 -627 -620 -256 579 921 -328 309 860 -339 -234 822 578...

output:

4937

result:

ok answer is '4937'

Test #14:

score: 0
Accepted
time: 4ms
memory: 6132kb

input:

1533
698889648 -578827493 -262105442 909404291 413315551 58485223 -40086811 836333943 717569157 925214479 -838945545 -792185683 632330806 621194734 -507381703 -423877991 654299697 951418620 547944701 873444638 241721237 927202957 854398029 -423274017 -184376941 -902734053 -263563815 14928752 -547732...

output:

15440282162

result:

ok answer is '15440282162'

Test #15:

score: 0
Accepted
time: 1ms
memory: 6204kb

input:

1469
566891435 276813107 -269833434 798483192 156520609 -133927715 -824768342 467777943 719040677 -178306126 869292199 -20032178 447035639 -216440617 310099776 -762488256 973771530 529876893 667856043 438737869 971410281 16311549 257997890 -670244740 923408434 -63379580 -538519438 -645400242 -898960...

output:

16395493396

result:

ok answer is '16395493396'

Test #16:

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

input:

1985
929560645 -529651056 -475800686 812657562 -531442420 -665813585 477022342 -681178771 -172360956 435952834 737340151 470553112 -254078904 -868064285 388742274 -781943845 -180919708 -704870932 832988034 -127732657 458792030 -574973007 -364164993 -282902313 371345439 925852561 894889178 -932584458...

output:

22468865212

result:

ok answer is '22468865212'

Test #17:

score: 0
Accepted
time: 1ms
memory: 5888kb

input:

1427
147812685 518852015 384950377 146696734 383897841 -822036009 939313442 -751240855 515911498 776875835 -955250092 -608998648 702505581 -824766834 305241341 -39739151 -542042485 756504727 -181829956 403267534 645928558 50075039 988049368 -112200079 136403043 163248263 -851994349 879461710 -656335...

output:

302077185

result:

ok answer is '302077185'

Test #18:

score: 0
Accepted
time: 1ms
memory: 6148kb

input:

1450
470278047 773767752 990000080 -242116879 96288230 725638114 -61674317 -29899397 -32045069 802312805 -78083811 880664444 -346924816 -378420987 321633829 -842390774 -982647296 181780517 223588203 -662717337 525318314 -983342425 455920417 -69942256 651090836 910589323 -89662928 829196601 308210953...

output:

-18964546

result:

ok answer is '-18964546'

Test #19:

score: 0
Accepted
time: 1ms
memory: 7204kb

input:

1984
-568212242 575162077 -514770035 91825555 -645483562 -88733636 -880513486 429840581 835176245 -798940559 -511618216 -546468807 -325535970 -407573577 7011476 377714211 -599939502 119546053 49386463 570070856 -625133729 -466851340 724664580 7469856 893754968 635980938 -684162381 -750809832 6542638...

output:

-379863843

result:

ok answer is '-379863843'

Test #20:

score: 0
Accepted
time: 3ms
memory: 5360kb

input:

1116
601089292 579405688 -94377208 -98449065 423956902 -141443365 -229969880 -552546445 -780569369 646077425 129152676 -990833249 741168117 951542848 -83805503 -900209259 802951634 679032229 691376377 322278836 -231836349 71125826 451473271 418286372 -528321291 -243992311 702148477 694048272 -602910...

output:

677927233

result:

ok answer is '677927233'

Test #21:

score: 0
Accepted
time: 1ms
memory: 6208kb

input:

1514
-202658408 -599206472 -778289097 -196138201 -262772777 -180575986 376523861 -861306821 806965699 -657400270 -324321996 407114312 794163634 -842992469 414474658 -651202810 -170876621 -792083249 -489515314 -610070836 -391591906 -530125541 -727298001 -490140733 570832879 908935420 480988436 763222...

output:

-719559045

result:

ok answer is '-719559045'

Test #22:

score: 0
Accepted
time: 1ms
memory: 5140kb

input:

1046
902611092 -521004526 825136261 -267972239 -760856021 -199211210 -611730574 -723252373 963196809 -236215049 -322252031 -697293486 453441159 533780756 416726473 33130619 -333554520 838909737 333185492 22049119 -655398717 563046708 -797762479 -326683660 -724697806 -63396727 -437993103 193712632 64...

output:

-1433631367

result:

ok answer is '-1433631367'

Test #23:

score: 0
Accepted
time: 3ms
memory: 5620kb

input:

1251
671462714 809084646 650554870 -613452217 -610655284 306572566 -718515841 -610006678 -230999501 888582287 -723016106 -235311276 -450319766 -107187298 -593814272 23299531 -278309634 -709456072 -442874093 -330486263 -144651571 -256651233 27029982 -470161943 981840278 -816767304 386778821 -21407260...

output:

-316335426

result:

ok answer is '-316335426'

Test #24:

score: -100
Time Limit Exceeded

input:

160417
660077889 -939582949 -886464413 437646629 952348168 783950666 565300102 257525155 -822686209 408804377 178911152 501752515 -184917585 -844382657 558189506 953563805 -612679398 -946423368 558776016 -231391063 51211054 -10951300 -285189680 11073219 496729876 33597082 -5269524 565098299 -8045184...

output:


result: