QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358838 | #112. Bulldozer | Dimash | 0 | 2ms | 3972kb | C++20 | 2.4kb | 2024-03-20 02:07:16 | 2024-03-20 02:07:16 |
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});
}
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%