QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#358838#112. BulldozerDimash0 2ms3972kbC++202.4kb2024-03-20 02:07:162024-03-20 02:07:16

Judging History

This is the latest submission verdict.

  • [2024-03-20 02:07:16]
  • Judged
  • Verdict: 0
  • Time: 2ms
  • Memory: 3972kb
  • [2024-03-20 02:07:16]
  • 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});
    }
    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();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: 3744kb

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: 3708kb

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: 3688kb

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: 1ms
memory: 3644kb

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: 3748kb

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: 3648kb

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: 1ms
memory: 3700kb

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: 1ms
memory: 3744kb

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: 3700kb

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: 1ms
memory: 3568kb

input:

1
0 0 -1

output:

0

result:

ok single line: '0'

Test #12:

score: -5
Wrong Answer
time: 0ms
memory: 3604kb

input:

1
0 0 1

output:

0

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #16:

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

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: 2ms
memory: 3944kb

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: 3644kb

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: 3972kb

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: 3944kb

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: 3784kb

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: 3768kb

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: 3704kb

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: 3940kb

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: 3744kb

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: 0ms
memory: 3560kb

input:

1
0 0 -1

output:

0

result:

ok single line: '0'

Test #27:

score: -20
Wrong Answer
time: 1ms
memory: 3632kb

input:

1
0 0 1

output:

0

result:

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

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%