QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780952 | #112. Bulldozer | lam | 5 | 42ms | 3736kb | C++14 | 1.7kb | 2024-11-25 14:08:50 | 2024-11-25 14:08:51 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ii array<int, 3>
using namespace std;
const int maxn = 2005;
int n, ans = 0;
array<int, 3> a[maxn], b[maxn];
template <typename T>
struct Point {
T x;
T y;
};
Point<ld> X, Y;
template <typename T>
T distance_point_to_line(const Point<T>& P, const Point<T>& A, const Point<T>& B) {
T dx = B.x - A.x;
T dy = B.y - A.y;
T numerator = (dy * (P.x - A.x) - dx * (P.y - A.y));
T denominator = sqrt(dx * dx + dy * dy);
return numerator / denominator;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("TRUFFLE.inp", "r", stdin);
// freopen("TRUFFLE.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i][0] >> a[i][1] >> a[i][2],
b[i] = a[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for (int k = 1, cur = 0; k <= n; k++)
{
cur = max(cur, 0ll) + b[k][2];
ans = max(ans, cur);
}
int pre = ans;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
{
X.x = a[i][0];
X.y = a[i][1];
Y.x = a[j][0];
Y.y = a[j][1];
sort(b + 1, b + n + 1, [](ii a, ii b){
Point<ld> Z;
Z.x = a[0];
Z.y = a[1];
Point<ld> T;
T.x = b[0];
T.y = b[1];
return distance_point_to_line<ld>(Z, X, Y) < distance_point_to_line<ld>(T, X, Y);
});
}
assert(ans == pre);
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 26ms
memory: 3664kb
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: 5
Accepted
time: 26ms
memory: 3652kb
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: 5
Accepted
time: 26ms
memory: 3684kb
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: 5
Accepted
time: 26ms
memory: 3584kb
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: 5
Accepted
time: 26ms
memory: 3664kb
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: 5
Accepted
time: 26ms
memory: 3664kb
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: 5
Accepted
time: 26ms
memory: 3680kb
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: 5
Accepted
time: 22ms
memory: 3680kb
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: 5
Accepted
time: 26ms
memory: 3604kb
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: 5
Accepted
time: 26ms
memory: 3680kb
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: 5
Accepted
time: 0ms
memory: 3736kb
input:
1 0 0 -1
output:
0
result:
ok single line: '0'
Test #12:
score: 5
Accepted
time: 0ms
memory: 3684kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #13:
score: 5
Accepted
time: 0ms
memory: 3596kb
input:
2 0 0 1 1 0 -1
output:
1
result:
ok single line: '1'
Test #14:
score: 5
Accepted
time: 0ms
memory: 3728kb
input:
2 0 0 1 1 0 1
output:
2
result:
ok single line: '2'
Test #15:
score: 5
Accepted
time: 0ms
memory: 3660kb
input:
3 0 0 2 1 0 -1 2 0 2
output:
3
result:
ok single line: '3'
Subtask #2:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 42ms
memory: 3604kb
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:
5636481522
result:
wrong answer 1st lines differ - expected: '8062662362', found: '5636481522'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%