QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358840 | #112. Bulldozer | Dimash | 25 | 2ms | 4000kb | C++20 | 2.5kb | 2024-03-20 02:08:07 | 2024-03-20 02:08:07 |
Judging History
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%