QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#551577 | #2338. Beautiful Bridges | RngBased# | AC ✓ | 190ms | 4064kb | C++20 | 2.3kb | 2024-09-07 17:24:15 | 2024-09-07 17:24:15 |
Judging History
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'