QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#380618#8572. Passing Gameucup-team1134#TL 604ms12800kbC++234.5kb2024-04-07 06:50:132024-04-07 06:50:13

Judging History

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

  • [2024-04-07 06:50:13]
  • 评测
  • 测评结果:TL
  • 用时:604ms
  • 内存:12800kb
  • [2024-04-07 06:50:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005;
const ll INF=1LL<<61;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

//dynamic CHT MIN

/**
 * Author: Simon Lindholm
 * Date: 2017-04-20
 * License: CC0
 * Source: own work
 * Description: Container where you can add lines of the form kx+m, and query maximum values at points x.
 *  Useful for dynamic programming (``convex hull trick'').
 * Time: O(\log N)
 * Status: stress-tested
 */
#pragma once

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct LineContainerMIN : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = inf, 0;
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        k*=-1;m*=-1;
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return -(l.k * x + l.m);
    }
};

ll dp[MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        ll N,K;cin>>N>>K;
        chmin(K,62LL);
        vector<array<ll,3>> S(N);
        for(int i=0;i<N;i++) cin>>S[i][0];
        for(int i=0;i<N;i++) cin>>S[i][1];
        for(int i=0;i<N;i++) S[i][2]=i;
        sort(all(S));
        vector<array<ll,3>> T;
        int stt=-1,goo=-1;
        for(int i=0;i<N;i++){
            if(S[i][2]==0){
                stt=i;
            }
            if(S[i][2]==N-1){
                goo=i;
            }
        }
        T.push_back(S[stt]);
        {
            ll la=S[stt][1];
            for(int i=stt-1;i>=0;i--){
                if(chmin(la,S[i][1])) T.push_back(S[i]);
                else if(i==goo) T.push_back(S[i]);
            }
        }
        {
            ll la=S[stt][1];
            for(int i=stt+1;i<si(S);i++){
                if(chmin(la,S[i][1])) T.push_back(S[i]);
                else if(i==goo) T.push_back(S[i]);
            }
        }
        int bi=N-1;
        sort(all(T));
        S=T;
        //for(auto [a,b,c]:S) cout<<a<<" "<<b<<" "<<c<<endl;
        N=si(S);
        stt=-1;goo=-1;
        for(int i=0;i<N;i++){
            if(S[i][2]==0){
                stt=i;
            }
            if(S[i][2]==bi){
                goo=i;
            }
        }
        //cout<<stt<<" "<<goo<<endl;
        for(int i=0;i<MAX;i++){
            dp[i]=INF;
        }
        dp[stt]=0;
        
        for(int t=0;t<=K;t++){
            bool upd=false;
            vector<ll> neL(N,INF),neR(N,INF);
            {
                LineContainerMIN cht;
                for(int i=0;i<N;i++){
                    neR[i]=dp[i];
                    auto [x,v,iii]=S[i];
                    if(i>=stt&&si(cht)) chmin(neR[i],cht.query(x));
                    if(neR[i]!=INF&&neR[i]<dp[goo]) cht.add(v,v*(-x)+neR[i]);
                }
            }
            {
                LineContainerMIN cht;
                for(int i=N-1;i>=0;i--){
                    neL[i]=dp[i];
                    auto [x,v,iii]=S[i];
                    if(i<=stt&&si(cht)) chmin(neL[i],cht.query(-x));
                    if(neL[i]!=INF&&neL[i]<dp[goo]) cht.add(v,v*x+neL[i]);
                }
            }
            for(int i=0;i<N;i++){
                if(min(neL[i],neR[i])<dp[goo]&&chmin(dp[i],min(neL[i],neR[i]))) upd=true;
            }
            if(!upd) break;
        }
        
        cout<<dp[goo]<<"\n";
    }
}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6140kb

input:

2
4 2
3 2 1 6
3 1 1 3
2 0
1 2
1 2

output:

7
1

result:

ok 2 number(s): "7 1"

Test #2:

score: 0
Accepted
time: 63ms
memory: 12392kb

input:

1
300000 204334
809492393 304618667 173130445 377106790 364888630 949045125 622060683 557772818 216607577 848817467 862855568 507840723 120816645 639713488 741781998 682531787 685261161 601686403 355792373 162819930 710057718 234560726 998604853 678957602 485413982 855985802 109303681 979706626 4822...

output:

31313390701066

result:

ok 1 number(s): "31313390701066"

Test #3:

score: 0
Accepted
time: 55ms
memory: 8240kb

input:

3
100000 65460
217141764 710454586 789075415 24849107 685675008 839804815 638763480 327755609 43827967 390187172 301370841 622696676 598237196 232099091 211987715 416876077 572665966 73382836 520033984 808399404 752832432 341795744 434460344 535426588 136624537 997406768 297342165 558882675 26863877...

output:

70635841128944
47230361360721
59110547802683

result:

ok 3 number(s): "70635841128944 47230361360721 59110547802683"

Test #4:

score: 0
Accepted
time: 58ms
memory: 12800kb

input:

1
300000 101975
207258305 525434317 528778163 645316642 562113679 143398489 9114413 669854123 106324041 841914487 21419012 308025536 689200225 263298218 39377353 860366080 24610184 43404209 529054797 902238799 422737070 484129934 967667618 953541323 338625285 115085955 363490839 998893783 877857789 ...

output:

40311829457542

result:

ok 1 number(s): "40311829457542"

Test #5:

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

input:

18
17 0
500000000 499999997 500000010 499999965 500000118 499999609 500001291 499995739 500014064 499953589 500153157 499494579 501667889 494495965 518163316 440061055 697798520
197798520 59938945 18163316 5504035 1667889 505421 153157 46411 14064 4261 1291 391 118 35 10 3 1
17 1
500000000 499999997...

output:

15506866876
14901483521
14901483521
14596599454
14596599454
14327495899
14327495899
14069829018
14069829018
13814295534
13814295534
13559037370
13559037370
13303815695
13303815695
13061698660
13061698660
13061698660

result:

ok 18 numbers

Test #6:

score: 0
Accepted
time: 62ms
memory: 12428kb

input:

1
300000 108311
562733523 631963246 813519221 169288073 117366252 527887631 958029417 190367625 583075950 97173270 896048212 131308006 37400006 90012864 923307076 279518077 383193505 134227338 223315078 230865002 126513901 226753074 767298214 632275980 328061909 158106292 275417458 205909246 6796599...

output:

22530954433990

result:

ok 1 number(s): "22530954433990"

Test #7:

score: 0
Accepted
time: 604ms
memory: 5900kb

input:

6000
50 9
134170081 235040736 405102476 567954026 351391400 872095141 116079799 935104039 779623552 857355273 642352783 394389351 10847154 403727586 104520573 266338849 213345479 719882827 836874283 973992590 698097800 821674140 408510849 363267881 10753022 371526254 123631785 246871721 505280626 29...

output:

30096348366675791
46069208396039888
43208901362730729
70517421587512986
11224815513692355
71475323642044669
1805862419831112
135052117577413332
26429620406592108
30539122715657614
7984965510320702
45549957862209120
42689412604990122
11269234889588471
80025912449049377
62081070915081025
4881768842034...

result:

ok 6000 numbers

Test #8:

score: 0
Accepted
time: 60ms
memory: 8320kb

input:

3
100000 29147
500000000 597145750 552984982 372885743 640231243 733918327 800174654 803027973 174812114 914218248 958491647 953654602 654712814 719285245 331288273 879947652 879757804 768921697 826703535 228697076 180453233 681236422 977876007 50434656 229471634 830980737 12014073 250160020 4486414...

output:

13061698660
13061698660
13061698660

result:

ok 3 number(s): "13061698660 13061698660 13061698660"

Test #9:

score: -100
Time Limit Exceeded

input:

30000
10 10
802030518 640274071 71550121 799843967 796619138 223219513 312183499 673542337 879397647 631413076
598196518 983359971 96204862 446173607 402690754 668171337 905549873 566661387 434495917 150918417
10 10
224422012 525305826 404334728 998133227 59632864 62611196 296576565 812713672 614679...

output:

69273774453668369
15440670445128286
192723941525693508
75675642974614068
36131012282542320
85171320762046356
27782956555892610
12331410768391077
241652836554719225
121097012285620735
382589380847694270
12204787868953675
98646491955517787
1209132821823955
27110849050473250
137126106329510200
13480620...

result: