QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780955#112. Bulldozerlam5 42ms3736kbC++141.7kb2024-11-25 14:09:142024-11-25 14:09:17

Judging History

This is the latest submission verdict.

  • [2024-11-25 14:09:17]
  • Judged
  • Verdict: 5
  • Time: 42ms
  • Memory: 3736kb
  • [2024-11-25 14:09:14]
  • Submitted

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);
                });

        }
    cout << ans;
}


详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 23ms
memory: 3720kb

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: 27ms
memory: 3596kb

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

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

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

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

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

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: 27ms
memory: 3720kb

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

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

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

input:

1
0 0 -1

output:

0

result:

ok single line: '0'

Test #12:

score: 5
Accepted
time: 0ms
memory: 3716kb

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #13:

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

input:

2
0 0 1
1 0 -1

output:

1

result:

ok single line: '1'

Test #14:

score: 5
Accepted
time: 0ms
memory: 3588kb

input:

2
0 0 1
1 0 1

output:

2

result:

ok single line: '2'

Test #15:

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

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

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%