QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358840#112. BulldozerDimash25 2ms4000kbC++202.5kb2024-03-20 02:08:072024-03-20 02:08:07

Judging History

This is the latest submission verdict.

  • [2024-03-20 02:08:07]
  • Judged
  • Verdict: 25
  • Time: 2ms
  • Memory: 4000kb
  • [2024-03-20 02:08:07]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5+ 5, MOD = 998244353;
#define int ll
int n,pos[N],t[N];
ll x[N],y[N],w[N];
vector<array<ll,3>> a;
void test() {
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i] >> w[i];
        a.push_back({x[i],-y[i],i});
    }
    if(n == 1){
        cout << max(0ll,w[1]) << '\n';
        return;
    }
    sort(a.begin(),a.end());
    for(int i = 0;i < (int)a.size();i++){
        pos[a[i][2]] = i + 1;
        t[i + 1] = a[i][2];
    }
    vector<pair<long double,pair<int,int>>> cur;
    for(int i = 1;i <= n;i++){
        for(int j = i+1;j <= n;j++){
            long double val = (long double)(y[j]-y[i]) / (long double)(x[j] - x[i]);
            cur.push_back({val,{i,j}});
        }
    }
    ll res = 0;
    sort(cur.rbegin(),cur.rend());
    for(int i = 0;i < (int)cur.size();i++){
        vector<pair<int,int>> ss;
        for(int j = i;j <= (int)cur.size();j++){
            if(j == (int)cur.size() || cur[j].first != cur[i].first){
                i = j - 1;
                break;
            }
            int L = min(pos[cur[j].second.first], pos[cur[j].second.second]), R = max(pos[cur[j].second.first],
                                                                                      pos[cur[j].second.second]);
            ss.push_back({L,R});
        }
        vector<ll> sums;
        sort(ss.begin(),ss.end());
        ll mn = 0,curs = 0;
        ll max_checked;
        for(int j = 0;j < (int)ss.size();j++) {
            if (j && max_checked >= ss[j].second) continue;
            int mx = ss[j].second;
            for (int k = j; k <= (int) ss.size(); k++) {
                if (k == (int) ss.size() || ss[k].first != ss[j].first) {
                    j = k - 1;
                    break;
                }
                max_checked = ss[k].second;
                mx = ss[k].second;
            }
            int l = ss[j].first, r = mx;
            while (l < r) {
                swap(t[l], t[r]);
                pos[t[l]] = l;
                pos[t[r]] = r;
                l++;
                r--;
            }
        }
        for(int j = 1;j <= n;j++){
            curs += w[t[j]];
            res = max(res,curs - mn);
            mn = min(mn,curs);
        }
    }
    cout << res << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while(T--){
        test();
    }
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3944kb

input:

100
547397735 0 -701876985
-994704489 0 -137482041
657756917 0 134137206
902929348 0 848664068
-942595218 0 905496420
-885718358 0 -183102425
-133322590 0 -765735957
40517489 0 137314145
-651698207 0 -755087111
-995622477 0 -437346891
905467861 0 -331241604
119881570 0 -555661137
-489890101 0 554937...

output:

3177735978

result:

ok single line: '3177735978'

Test #2:

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

input:

100
-261161481 0 -914392661
-666405901 0 -41566748
66756925 0 -998443149
952300068 0 573223358
309115993 0 -71109795
-437248002 0 -998530659
8869283 0 -747615449
49181126 0 438208683
581940102 0 716960639
77140827 0 -652930885
133126337 0 -222491793
867541743 0 390837222
167016881 0 -843021041
88598...

output:

4233982289

result:

ok single line: '4233982289'

Test #3:

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

input:

100
-222857036 0 974268066
-963708956 0 571111453
429775825 0 -488478252
-890405877 0 644217358
-145476249 0 165475563
29568362 0 -871157181
-590835003 0 -367690261
-949688033 0 862094564
-829133448 0 101313815
927649348 0 146819177
750589423 0 -857789865
986972806 0 -890509036
-345137050 0 -9560614...

output:

7862036314

result:

ok single line: '7862036314'

Test #4:

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

input:

100
-765834815 0 793761317
-590714711 0 877069467
875088436 0 -731140189
585062563 0 881661413
-43312535 0 178316122
-332128714 0 -301531685
105303357 0 -34868508
-530964546 0 586283855
-239824340 0 -697091034
939764764 0 -594915278
-792023779 0 697168838
-375624278 0 -609724856
24743017 0 -93058205...

output:

8526209158

result:

ok single line: '8526209158'

Test #5:

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

input:

100
-636880431 0 465934512
903773040 0 781918212
531633762 0 -668342878
124109692 0 -506553188
-291869987 0 -200916555
-647982335 0 -507011413
-933154753 0 -736194510
-501962655 0 103499621
454996768 0 -124979750
549671906 0 752281199
-292851807 0 -841066828
-146499552 0 -257697933
-975417825 0 -932...

output:

2625361444

result:

ok single line: '2625361444'

Test #6:

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

input:

100
-857394336 0 -944755079
-780006622 0 -139547826
-2560270 0 349126587
282599103 0 -11738099
-460221770 0 625520397
36526360 0 -996812076
-811403082 0 -125116484
380912231 0 983338070
-416153287 0 642400465
336292294 0 -651556660
-709948524 0 -990304229
823950984 0 -930807543
-895326122 0 47665213...

output:

3874129803

result:

ok single line: '3874129803'

Test #7:

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

input:

100
-975151282 0 -465136862
422840744 0 -605491521
-442164576 0 264906611
-547427714 0 -91634247
-431211607 0 120363028
-381891858 0 127165539
-954954108 0 -819088685
138832911 0 -448464992
-766994308 0 -729401566
436164370 0 961590254
-449775864 0 -247831509
-666671795 0 -842063887
-923743845 0 173...

output:

4847418387

result:

ok single line: '4847418387'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3744kb

input:

100
-669822387 0 922925305
-883818451 0 8479702
98172896 0 46045113
936068983 0 -503493338
-430857057 0 481009228
-323595794 0 -776889225
321116637 0 68975670
282010402 0 168401391
-584979742 0 -846678475
-885465473 0 -12475048
-997014156 0 -663885649
-107523102 0 -624884016
153462146 0 508478755
-8...

output:

2455488903

result:

ok single line: '2455488903'

Test #9:

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

input:

100
813401424 0 -862325176
-421905957 0 734638464
666910031 0 -842119169
-833302447 0 -111841505
720440241 0 772103976
400327483 0 -148258200
-435748418 0 906697520
630665390 0 986798888
-45117776 0 894199888
747899578 0 599624948
34177986 0 617453134
-985626489 0 -29101360
-46259591 0 364442775
851...

output:

6550560680

result:

ok single line: '6550560680'

Test #10:

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

input:

100
-925110578 0 230631768
-430445107 0 169066762
-974931672 0 -480757607
-863283656 0 380412476
378972090 0 -402256816
-496070525 0 241369732
-5219166 0 -593344355
-687047875 0 -787363637
-784209470 0 -344936103
592586642 0 -932899477
783917014 0 262250096
-932557920 0 374017595
945116339 0 -258993...

output:

4278493522

result:

ok single line: '4278493522'

Test #11:

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

input:

1
0 0 -1

output:

0

result:

ok single line: '0'

Test #12:

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

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #13:

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

input:

2
0 0 1
1 0 -1

output:

1

result:

ok single line: '1'

Test #14:

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

input:

2
0 0 1
1 0 1

output:

2

result:

ok single line: '2'

Test #15:

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

input:

3
0 0 2
1 0 -1
2 0 2

output:

3

result:

ok single line: '3'

Subtask #2:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 2ms
memory: 3984kb

input:

100
-24309550 482269965 -297648951
253448360 -441723643 -920713212
324597788 390083514 -865804754
713394653 -881475679 678850273
-445282104 369972896 691296843
69042891 -867513631 -239602542
-391732493 330791482 17449017
279658315 890578483 565738698
625283527 15481214 530839875
592822547 33796172 4...

output:

8062662362

result:

ok single line: '8062662362'

Test #17:

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

input:

100
-257587011 400852223 -220309345
-875500067 -86782621 326270594
-414287853 -977479920 -984533791
-635666918 -708630100 326066280
-615040019 -993541890 -685301992
-760310577 221302942 45160524
-990846996 351043755 -648825880
-918729931 -379977547 911808427
252530998 107120801 -919405596
507878869 ...

output:

7374350612

result:

ok single line: '7374350612'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3752kb

input:

100
-234721699 646933168 -338655575
-806569531 -71216264 -872209889
740102166 -655865625 80137029
-619042650 86451086 919481887
-613310459 862325871 299940063
-486792319 385052870 -459562867
-877904368 -297131478 447851188
199060395 -82554072 -131371354
-952281361 -710915129 307615240
-507291693 907...

output:

6210932418

result:

ok single line: '6210932418'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3984kb

input:

100
-573155230 -21482599 137188437
-858318223 -627279123 74329590
-17310327 -177777278 788416416
-670979585 820505465 -787614633
562566093 273531226 733397305
-64307790 599053244 -297009699
817165433 -369316382 924081906
720802586 596624938 351428871
115928798 523348194 -586662700
-885459046 -895204...

output:

8054120128

result:

ok single line: '8054120128'

Test #20:

score: 0
Accepted
time: 2ms
memory: 3788kb

input:

100
701468719 174754273 994891446
508373256 -732987695 648967734
369948378 -700859918 834543102
-862822283 -588546632 -394089051
-880849099 -911153118 -293420654
861677968 917107626 824561386
-359587638 -857777409 -913592764
-135640113 -867460034 933004325
-971454790 -711909514 -274071917
953354587 ...

output:

11634325865

result:

ok single line: '11634325865'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3920kb

input:

100
-406079738 55160150 -920565361
725055282 878590579 -800311783
-670162535 901392505 240442550
179342318 -384964487 -877645265
592925162 -971845016 -313276130
-659126723 30771322 771426239
-749159311 433142945 -927853693
-676435064 -378708256 -634922247
-486642852 229623957 530273029
-269137808 57...

output:

5685526749

result:

ok single line: '5685526749'

Test #22:

score: 0
Accepted
time: 2ms
memory: 3944kb

input:

100
-689190423 220983861 913342760
-807787476 31872295 443021122
-815582432 -456178077 894438019
326141220 -885526038 -427240265
390679145 408965343 -859292305
-928486438 685567377 248489199
-45211459 -700556605 17089679
-28845394 -9042916 -609052379
-469176499 481816321 -964805208
-918568308 448434...

output:

5621356954

result:

ok single line: '5621356954'

Test #23:

score: 0
Accepted
time: 2ms
memory: 4000kb

input:

100
187164857 900233795 990568533
-125876794 892832559 -940816798
-321878196 394069566 -244480066
-670273914 544753218 376169540
910151452 -861989228 -628283308
352749124 -819374074 741277319
-344455996 -217000212 -944332393
93217857 -174981978 -180151861
94543655 256400293 -888939691
782508726 -969...

output:

5036576367

result:

ok single line: '5036576367'

Test #24:

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

input:

100
531363827 -977931429 -76627691
566440726 -235229527 337777732
89516229 -489823739 -691867132
907305820 -945880242 -285222604
-183193668 -54409760 574440897
985173840 -947464549 358402992
38982981 -262700773 -810245538
193675330 -701123831 627792386
738870352 -634028033 -781105055
187273959 -5919...

output:

6460320517

result:

ok single line: '6460320517'

Test #25:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

100
-353174997 -351995784 -310183082
654678384 947350572 758744270
37126054 247124163 -388016820
282286988 -992350460 -723589942
531405766 108105766 52078769
-344987066 557794460 305053304
787276939 -576929156 212556717
34490507 -937159146 -794206787
368163585 -217235651 952032589
11623915 -65802595...

output:

8695946466

result:

ok single line: '8695946466'

Test #26:

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

input:

1
0 0 -1

output:

0

result:

ok single line: '0'

Test #27:

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

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #28:

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

input:

2
0 0 1
0 1 -1

output:

1

result:

ok single line: '1'

Test #29:

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

input:

2
0 0 1
0 1 1

output:

2

result:

ok single line: '2'

Test #30:

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

input:

3
-196970608 -259062089 -315946900
-880312834 -824169703 695651137
-952951255 -453975245 -456334228

output:

695651137

result:

ok single line: '695651137'

Test #31:

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

input:

3
-904399232 197805285 -409227852
252002501 -603959820 -265360818
-584036233 955522285 -606118177

output:

0

result:

ok single line: '0'

Test #32:

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

input:

3
819901047 -930259703 -717371546
2759216 -889603050 232484320
468055317 -559162010 -804576960

output:

232484320

result:

ok single line: '232484320'

Test #33:

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

input:

4
-567458435 413660811 672407797
-52833185 -976745057 -137512537
-29340005 53972841 544308705
258569846 423384165 -271529583

output:

1216716502

result:

ok single line: '1216716502'

Test #34:

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

input:

4
518389369 280627664 -140579924
180993080 505035811 -618512465
262205753 -850582688 287042495
-979026791 443616387 467523162

output:

754565657

result:

ok single line: '754565657'

Test #35:

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

input:

4
274532062 833467053 -966615189
-925171401 990038689 -995756842
289416482 515357887 651324863
268351706 -185994232 777557885

output:

1428882748

result:

ok single line: '1428882748'

Test #36:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

100
999995897 999996781 387343302
999999437 999992610 527391011
999991947 999994474 -910551312
999999463 999999736 668118168
999993157 999994934 -920412353
999992157 999998105 -166875630
999994880 999994494 -34207478
999999548 999995286 186618265
999992504 999997869 -412394547
999993966 999990034 -1...

output:

5774783260

result:

ok single line: '5774783260'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3704kb

input:

100
999996493 999999717 -472781015
999994959 999990741 140905225
999994650 999994580 -633697448
999991609 999990256 332595270
999994643 999992159 -940273142
999998356 999995944 820931402
999995182 999992871 49900922
999998560 999995066 -297060165
999995890 999993371 302610643
999991051 999990111 -39...

output:

5349621145

result:

ok single line: '5349621145'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3736kb

input:

100
999996766 999992490 453505086
999991515 999990542 940427001
999994183 999999012 -11420484
999991487 999999611 -74233226
999996867 999994200 -806223556
999995705 999990016 -614835757
999990422 999996065 144991311
999991280 999995560 990904650
999993900 999994975 -861802403
999993320 999993206 -26...

output:

3677208423

result:

ok single line: '3677208423'

Test #39:

score: 0
Accepted
time: 2ms
memory: 3908kb

input:

100
999997304 999976132 722531352
999995107 999982170 169518745
999972891 999976540 952713688
999993563 999971110 685110355
999975695 999998656 -268303225
999984363 999985910 620513241
999989119 999971583 -904296386
999984254 999973568 12812482
999970839 999974417 -918339267
999993144 999977062 9276...

output:

5977105563

result:

ok single line: '5977105563'

Test #40:

score: 0
Accepted
time: 2ms
memory: 3748kb

input:

100
999999169 999999051 -383683652
999980959 999999507 -985348244
999997987 999984305 -25350871
999988229 999977309 -877856183
999977336 999982164 -54215005
999972699 999976042 -687614217
999977586 999974999 -878345275
999998495 999979978 -737327920
999995249 999975086 -827194141
999998566 999982667...

output:

6835367472

result:

ok single line: '6835367472'

Test #41:

score: 0
Accepted
time: 2ms
memory: 3996kb

input:

100
999984857 999985986 -640170026
999970636 999991681 -676962001
999978008 999994375 -510401729
999993558 999978346 29019591
999995453 999979390 846553934
999984894 999976018 620917572
999985305 999995323 -544989750
999984696 999996168 -283354913
999990215 999997907 185604996
999996904 999988593 -7...

output:

4333146486

result:

ok single line: '4333146486'

Test #42:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

100
999999225 -999991217 -208451264
999992954 -999993173 416922694
999998159 -999997404 -7404135
999996216 -999996287 -909575478
999998443 -999994770 -216976385
999999357 -999995920 -437809902
999992923 -999991958 -104610811
999998216 -999996127 -210240999
999996573 -999996419 798518635
999990507 -9...

output:

6523024049

result:

ok single line: '6523024049'

Test #43:

score: 0
Accepted
time: 2ms
memory: 3688kb

input:

100
999991776 -999999334 967640434
999991338 -999993172 -190186773
999990062 -999995602 519679311
999993594 -999999552 -401926815
999997113 -999992848 579378433
999998071 -999999690 -930880408
999994837 -999994533 397702683
999991376 -999992886 382330402
999991617 -999999191 458945774
999998597 -999...

output:

10455034037

result:

ok single line: '10455034037'

Test #44:

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

input:

100
999990286 -999994852 418625557
999995278 -999994649 129945246
999996539 -999990841 -75937765
999990452 -999996981 -993418764
999999229 -999999560 -681685649
999999663 -999998984 956379334
999994363 -999991640 678308115
999991506 -999995106 -190675279
999997499 -999994424 -933464751
999992765 -99...

output:

4984723336

result:

ok single line: '4984723336'

Test #45:

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

input:

100
999984725 -999988306 -536811057
999989661 -999999586 -340234339
999998996 -999970775 264227748
999995573 -999984228 453536486
999997386 -999978819 928661040
999997790 -999980588 -628632997
999979079 -999983304 8085365
999999712 -999992217 969211153
999982598 -999993819 -889278875
999985109 -9999...

output:

6632131603

result:

ok single line: '6632131603'

Test #46:

score: 0
Accepted
time: 2ms
memory: 3920kb

input:

100
999982110 -999986664 -183347253
999991601 -999999175 -530124722
999975963 -999991567 466307188
999972696 -999988507 -362668221
999997697 -999975276 938733865
999991769 -999982056 -423829892
999973857 -999990868 845614831
999979704 -999987802 743243029
999990551 -999972594 -779457843
999979873 -9...

output:

12863801465

result:

ok single line: '12863801465'

Test #47:

score: 0
Accepted
time: 2ms
memory: 3924kb

input:

100
999996945 -999978386 -264026779
999995629 -999975267 980854424
999993270 -999989144 486333529
999974511 -999989174 -37989197
999974214 -999989181 -673130656
999995518 -999994174 -966863873
999980794 -999998733 -51946365
999997607 -999992729 -955610480
999999807 -999993631 491683821
999988342 -99...

output:

6170174103

result:

ok single line: '6170174103'

Subtask #3:

score: 0
Time Limit Exceeded

Dependency #2:

100%
Accepted

Test #48:

score: 0
Time Limit Exceeded

input:

2000
89376854 379063415 -944003713
471827852 -789362482 -184369700
917771217 861434859 -951123027
388529816 150284383 863099328
-684844756 709695302 -812548755
-464667377 -991797883 -48791570
-100872644 745870335 301027897
863501557 763500779 -222414774
-778833050 168341796 277632677
-816853769 -167...

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%