QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#551577#2338. Beautiful BridgesRngBased#AC ✓190ms4064kbC++202.3kb2024-09-07 17:24:152024-09-07 17:24:15

Judging History

你现在查看的是最新测评结果

  • [2024-09-07 17:24:15]
  • 评测
  • 测评结果:AC
  • 用时:190ms
  • 内存:4064kb
  • [2024-09-07 17:24:15]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;

const ll INF = 1'000'000'000;

pll intersect(pll p, pll q)
{
    return pll(max(p.F, q.F), min(p.S, q.S));
}
// solve ax^2 + bx + c <= 0
ll check_root(ll a, ll b, ll c, ll r, int dir)
{
    for (int i = -2; i <= 2; i++)
    {
        ll x = r + i * dir;
        if (a * x * x + b * x + c <= 0)
            return x;
    }
    return dir * INF;
}
pll solve_quadratic(ll a, ll b, ll c)
{
    assert(a >= 0);
    ll D = b * b - 4 * a * c;
    if (D < 0)
        return pll(INF, -INF);
    double r1 = (-b - sqrt(D)) / (2.0 * a);
    double r2 = (-b + sqrt(D)) / (2.0 * a);
    
    return pll(check_root(a, b, c, r1, +1),
               check_root(a, b, c, r2, -1));
}
pll under_arch(ll xi, ll x, ll yi, ll h)
{
    return solve_quadratic(1, 4 * (xi - x + yi - h), 4 * (xi - x) * (xi - x) + 4 * (yi - h) * (yi - h));
}

ll n, h, a, b, x[10005], y[10005], dp[10005], in[10005];
vector<int> ord;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> h >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    for (int i = 1; i <= n; i++)
        ord.emplace_back(i);
    sort(all(ord), [&](int i, int j) { return y[i] > y[j]; });
    dp[1] = a * (h - y[1]);
    for (int i = 2; i <= n; i++)
    {
        dp[i] = INF * INF;
        pll range = pll(-INF, INF);

        fill(in + 1, in + 1 + n, 0);
        auto increment = [&](int j)
        {
            ++in[j];
            if (in[j] == 2)
            {   
                range = intersect(range, under_arch(x[j], x[i], y[j], h));
            }
        };

        int jdx = 0;
        for (int j = i; j >= 1; j--)
        {
            increment(j);
            while (jdx < n && x[i] - x[j] >= 2 * (h - y[ord[jdx]]))
                increment(ord[jdx]), jdx++;

            if (j != i && range.F <= x[i] - x[j] && x[i] - x[j] <= range.S)
                dp[i] = min(dp[i], dp[j] + b * (x[i] - x[j]) * (x[i] - x[j]) + a * (h - y[i]));
        }
    }
    if (dp[n] == INF * INF)
        cout << "impossible\n";
    else 
        cout << dp[n] << '\n';


}


详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

5 60 18 2
0 0
20 20
30 10
50 30
70 20

output:

6460

result:

ok single line: '6460'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

4 10 1 1
0 0
1 9
9 9
10 0

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

2 1 1 1
0 0
2 0

output:

6

result:

ok single line: '6'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

2 1 1 1
0 0
3 0

output:

impossible

result:

ok single line: 'impossible'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

4 5 100 1
0 0
1 3
9 3
10 0

output:

1100

result:

ok single line: '1100'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

4 5 1 100
0 0
1 3
9 3
10 0

output:

10010

result:

ok single line: '10010'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2 100000 10000 10000
0 0
100000 0

output:

100002000000000

result:

ok single line: '100002000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

13 43 1 5
3 26
4 25
10 23
11 0
23 2
49 20
64 2
68 0
83 24
84 17
91 33
92 6
97 33

output:

7348

result:

ok single line: '7348'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

12 29 5 1
4 26
5 18
15 15
27 26
31 12
40 0
46 19
67 4
68 2
77 1
83 12
89 10

output:

2134

result:

ok single line: '2134'

Test #10:

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

input:

18 99 5 1
0 10
4 5
9 9
15 0
37 16
38 7
39 5
43 2
53 12
57 18
61 1
64 5
70 12
74 13
78 16
86 19
89 3
99 15

output:

4586

result:

ok single line: '4586'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

18 60 1 4
0 12
4 37
9 5
14 52
15 54
31 31
34 34
43 36
49 44
59 53
60 18
67 23
70 12
76 15
83 53
96 41
99 52
100 45

output:

4745

result:

ok single line: '4745'

Test #12:

score: 0
Accepted
time: 181ms
memory: 4052kb

input:

10000 100000 9990 1
10 722
11 42
30 116
35 438
47 690
49 369
72 234
94 243
101 34
133 884
135 571
143 365
150 829
185 549
186 361
191 698
192 111
194 41
223 249
227 440
232 180
264 679
265 341
273 345
276 700
279 898
293 300
300 878
302 47
313 203
314 105
336 859
337 533
346 163
366 400
370 509
381 ...

output:

7290507173

result:

ok single line: '7290507173'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

17 54 5 1
7 31
18 15
24 41
28 23
35 45
55 32
56 48
57 17
61 49
67 4
76 5
80 53
84 7
90 51
91 44
94 24
95 40

output:

2597

result:

ok single line: '2597'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

19 96 4 1
8 1
10 20
11 16
16 15
20 20
21 13
35 6
45 10
50 17
62 13
64 11
70 19
78 0
79 15
81 3
83 11
85 9
92 6
93 2

output:

3567

result:

ok single line: '3567'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

46 6921 1 5259
15 461
20 821
65 608
87 39
104 304
113 602
122 16
147 527
169 858
190 358
231 743
266 361
316 222
344 492
371 263
406 508
436 500
437 353
447 293
537 870
539 30
557 206
561 617
578 360
638 240
639 310
661 641
687 82
715 783
721 801
727 627
744 770
747 457
842 51
843 72
846 11
856 407
...

output:

214911843

result:

ok single line: '214911843'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

153 7126 8741 1
0 984
6 824
8 426
19 975
23 440
27 940
35 178
40 614
48 465
50 366
54 102
56 833
63 463
72 817
95 633
101 547
106 900
110 178
112 692
122 427
143 648
144 184
145 944
146 732
151 939
153 556
154 208
155 451
170 522
177 999
183 864
190 4
194 19
200 449
203 219
206 556
209 912
211 217
2...

output:

108671638

result:

ok single line: '108671638'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

176 9909 4823 1
5 16
9 58
13 47
17 39
20 52
22 92
33 97
39 75
53 41
90 82
91 66
93 71
95 92
96 5
103 76
104 55
108 58
122 41
129 2
135 43
139 89
140 87
143 74
149 5
156 51
158 55
166 39
168 91
178 4
179 71
184 10
195 44
197 3
198 62
206 9
212 97
213 85
216 23
217 22
220 28
222 20
225 37
227 76
236 7...

output:

96353817

result:

ok single line: '96353817'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

143 680 1 3041
18 17
21 583
23 508
24 68
42 297
45 486
46 566
49 520
59 598
64 449
73 559
75 245
76 155
92 341
97 158
105 522
109 295
123 384
129 245
131 155
139 464
147 492
154 533
160 265
164 438
170 561
173 429
174 578
178 627
189 555
191 111
195 319
199 242
201 211
210 157
214 633
221 480
222 17...

output:

35751813

result:

ok single line: '35751813'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

135 2006 3400 1
7 290
9 13
25 455
32 365
38 84
39 495
67 511
99 62
112 112
115 905
117 145
122 136
128 960
131 6
136 861
141 535
168 172
177 287
179 976
189 216
196 425
212 944
214 20
219 73
229 706
234 666
240 421
245 855
291 87
301 470
305 30
310 172
316 91
323 233
326 784
336 902
342 625
349 157
...

output:

11558724

result:

ok single line: '11558724'

Test #20:

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

input:

150 9947 4020 1
0 66
4 82
9 31
12 16
21 37
27 74
30 39
31 43
32 86
36 61
37 67
49 20
54 20
55 6
57 0
60 31
68 10
74 44
77 39
81 26
92 96
97 43
109 26
120 97
125 18
128 27
130 88
135 88
138 41
154 76
158 53
200 85
205 47
228 40
230 2
235 54
238 30
241 61
257 79
260 7
264 14
269 86
271 65
276 80
277 1...

output:

80342836

result:

ok single line: '80342836'

Test #21:

score: 0
Accepted
time: 182ms
memory: 3980kb

input:

10000 100000 1 9996
1 968
15 875
33 917
65 530
71 801
73 530
74 556
84 845
93 56
105 315
128 515
142 707
175 816
188 199
200 179
202 913
213 761
214 488
259 72
281 80
285 921
312 579
329 536
330 600
351 41
353 257
356 641
357 49
359 646
361 864
373 417
375 117
380 951
385 713
409 494
416 641
419 788...

output:

19868581626

result:

ok single line: '19868581626'

Test #22:

score: 0
Accepted
time: 180ms
memory: 4040kb

input:

10000 100000 1 1
16 584
53 497
62 366
68 181
70 485
71 517
83 244
88 415
95 789
99 487
107 24
111 824
112 144
125 82
140 343
149 747
164 141
167 854
175 280
178 535
179 124
209 818
211 554
220 844
253 621
257 706
269 109
290 994
317 592
321 14
335 649
348 941
353 97
354 590
355 181
357 101
363 242
3...

output:

63092663

result:

ok single line: '63092663'

Test #23:

score: 0
Accepted
time: 190ms
memory: 4064kb

input:

10000 20000 10000 1
0 10000
1 9999
2 9998
3 9997
4 9996
5 9995
6 9994
7 9993
8 9992
9 9991
10 9990
11 9989
12 9988
13 9987
14 9986
15 9985
16 9984
17 9983
18 9982
19 9981
20 9980
21 9979
22 9978
23 9977
24 9976
25 9975
26 9974
27 9973
28 9972
29 9971
30 9970
31 9969
32 9968
33 9967
34 9966
35 9965
3...

output:

399970001

result:

ok single line: '399970001'

Test #24:

score: 0
Accepted
time: 180ms
memory: 4056kb

input:

10000 20000 10000 1
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
...

output:

399990001

result:

ok single line: '399990001'

Test #25:

score: 0
Accepted
time: 27ms
memory: 3632kb

input:

1398 15714 10000 93
14 4228
15 5598
78 9544
91 8436
106 4618
169 2778
210 2801
227 6622
361 8044
417 2494
422 1016
461 250
485 8874
575 4108
627 9353
783 6598
803 3951
860 6404
888 2623
930 8567
939 7521
987 6033
1009 2937
1206 993
1280 3854
1435 8355
1542 350
1653 2362
1700 3168
1783 1103
1837 3558...

output:

16166716468

result:

ok single line: '16166716468'

Test #26:

score: 0
Accepted
time: 45ms
memory: 3668kb

input:

1756 5259 10000 514
70 2859
83 628
149 667
206 3867
288 4379
311 907
325 2144
350 3773
384 1108
390 3714
403 1232
469 4529
521 3074
565 4907
567 1170
633 5019
688 3569
794 4250
828 106
1078 1017
1137 1780
1183 2154
1289 166
1557 3391
1594 302
1671 517
1727 1078
1788 3242
1940 2763
2013 2858
2017 330...

output:

17892638214

result:

ok single line: '17892638214'

Test #27:

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

input:

710 39725 10000 313
206 9792
697 2570
701 8131
769 4854
826 4717
861 758
1065 7029
1436 638
1440 5588
1764 7944
1800 9157
1819 3538
2116 5607
2280 3363
2873 1468
3245 4953
3518 4420
3781 52
4003 6744
4099 3534
4152 3126
4186 5229
4301 32
4341 163
4598 8983
4705 2837
4714 7823
4898 9328
4945 2938
520...

output:

63617025621

result:

ok single line: '63617025621'

Test #28:

score: 0
Accepted
time: 15ms
memory: 3676kb

input:

1080 19197 10000 774
149 8522
162 9933
186 7677
226 7891
308 538
341 4916
466 5838
569 8730
605 5339
723 9457
756 826
950 9290
995 3424
1039 2495
1190 4013
1345 9711
1373 7021
1570 1797
1630 2604
1701 6164
1753 6338
1798 392
1920 7370
2071 801
2143 551
2175 7364
2607 6087
2928 1908
3043 4417
3347 57...

output:

61691273594

result:

ok single line: '61691273594'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

33 76007 10000 84
7115 3466
7753 9094
11168 4974
11694 609
11853 7602
12016 370
12596 6766
16746 3996
18806 8647
21354 5725
22313 9989
23340 3677
25448 1432
30096 1457
38677 6920
49540 904
49931 5111
53998 6245
58544 7704
61441 7256
62018 1899
64123 8733
65558 7761
67917 8161
69467 2577
73984 10
753...

output:

53882247036

result:

ok single line: '53882247036'

Test #30:

score: 0
Accepted
time: 1ms
memory: 3648kb

input:

336 47468 10000 507
37 9643
443 7921
734 5315
1048 6306
1185 4000
1968 5472
2016 9799
2139 5972
2190 6781
2281 9340
2299 4103
3264 7614
3378 8903
3409 5506
3749 2132
3858 8604
4166 2008
4406 6067
4530 4230
4619 7881
5204 6196
5696 4302
5943 1884
6079 2174
6205 3581
6483 8712
7730 5328
8761 8760
8841...

output:

92432732465

result:

ok single line: '92432732465'