QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203546 | #2483. Roof Escape | DreamOn# | WA | 2ms | 6412kb | C++23 | 2.7kb | 2023-10-06 18:00:57 | 2023-10-06 18:00:58 |
Judging History
answer
#include <bits/stdc++.h>
#define MP(x, y) make_pair(x, y)
#define pii pair <int, int>
#define double long double
using namespace std;
const double eps = 1e-10;
int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while('0' <= c && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
#define Maxn 100005
int W, H, Sx, Sy, Ex, Ey;
double ans1, ans2, k, b;
vector <int> t[Maxn];
void calcLine() {
if(Sx == Ex) k = 1926000, b = Sx;
else {
k = (Sy - Ey) * 1.0 / (Sx - Ex);
b = Sy - k * Sx;
}
}
int main() {
W = read(); H = read(); Sx = read(); Sy = read(); Ex = read(); Ey = read();
ans1 = sqrt((Sx - Ex) * (Sx - Ex) + (Sy - Ey) * (Sy - Ey));
for(int i = 1; i <= H / 2; ++i) { // Attention it's a (H/2, W/2) matrix!
t[i].push_back(0);
for(int j = 1; j <= W / 2; ++j) t[i].push_back(read());
}
calcLine();
if(Sx > Ex) swap(Sx, Ex), swap(Sy, Ey);
for(double x = Sx + 1, y; x <= Ex - 1; x += 2) {
y = k * x + b;
if(fabs((y / 2) - (int)(y / 2)) > eps) { // Edge
int li = (ceil)(y / 2), lj = x / 2;
int ri = li, rj = lj + 1;
ans2 += fabs(t[li][lj] - t[ri][rj]);
// cerr << "???" << endl;
}
else { // Point
int ai = y / 2, aj = x / 2;
int bi = ai, bj = aj + 1;
int ci = ai + 1, cj = aj;
int di = ai + 1, dj = aj + 1;
int tmp[5] = {0, t[ai][aj], t[bi][bj], t[ci][cj], t[di][dj]};
sort(tmp + 1, tmp + 5);
int maxh = tmp[3];
if(k > 0) ans2 += abs(maxh - t[ai][aj]) + abs(maxh - t[di][dj]);
else ans2 += abs(maxh - t[bi][bj]) + abs(maxh - t[ci][cj]);
// cerr << "plog " << x << " " << y << " " << ans2 << " " << maxh << endl;
// cerr << "qlog " << ai << " " << bi << " " << ci << " " << di << endl;
// cerr << "elog " << aj << " " << bj << " " << cj << " " << dj << endl;
}
}
if(Sy > Ey) swap(Sx, Ex), swap(Sy, Ey);
// cerr << Sx << " " << Sy << " " << Ex << " " << Ey << endl;
for(double y = Sy + 1, x; y <= Ey - 1; y += 2) {
if(k == 1926000) x = Sx;
else x = (y - b) / k;
// cerr << "!!!" << x << endl;
if(fabs((x / 2) - (int)(x / 2)) > eps) { // Edge
int ui = y / 2, uj = (ceil)(x / 2);
int di = ui + 1, dj = uj;
ans2 += fabs(t[ui][uj] - t[di][dj]);
// cerr << "???" << endl;
}
}
cout << fixed << setprecision(10);
cout << ans1 + ans2 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6216kb
input:
4 26 1 1 3 25 0 1 0 5 5 5 0 1 2 1 4 1 5 0 0 0 1 0 6 4 3 2 5 4 1 5
output:
53.0831891576
result:
ok found '53.08319', expected '53.08319', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
8 8 1 7 7 1 2 3 2 0 2 1 1 2 1 2 0 0 0 0 0 1
output:
14.4852813742
result:
ok found '14.48528', expected '14.48528', error '0.00000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6312kb
input:
2 2 1 1 1 1 100
output:
0.0000000000
result:
ok found '0.00000', expected '0.00000', error '-0.00000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6256kb
input:
4 4 1 1 3 3 100 1 1 100
output:
2.8284271247
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 6256kb
input:
4 4 1 1 3 3 1 100 100 1
output:
200.8284271247
result:
ok found '200.82843', expected '200.82843', error '0.00000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
4 4 1 3 3 1 1 100 100 1
output:
2.8284271247
result:
ok found '2.82843', expected '2.82843', error '0.00000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 6316kb
input:
2 56 1 23 1 17 1 0 1 0 1 0 0 4 1 3 1 1 3 0 3 1 1 0 0 2 0 2 1 0 1 0 0 0
output:
10.0000000000
result:
ok found '10.00000', expected '10.00000', error '0.00000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 6308kb
input:
2 28 1 9 1 23 2 1 1 3 2 1 2 0 3 1 1 1 1 3
output:
23.0000000000
result:
ok found '23.00000', expected '23.00000', error '0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6268kb
input:
2 18 1 11 1 13 1 0 2 0 4 0 2 2 4
output:
4.0000000000
result:
ok found '4.00000', expected '4.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 6232kb
input:
2 400 1 133 1 399 3 6 2 3 0 2 0 3 6 1 6 3 1 5 3 1 6 3 0 2 4 3 3 2 3 0 6 4 2 5 0 3 1 1 3 0 1 3 0 3 5 2 1 2 4 5 0 2 1 0 4 7 3 1 6 4 3 5 2 0 0 3 2 0 2 7 1 0 2 1 2 0 3 0 3 0 6 2 0 4 2 0 3 3 5 0 3 6 3 0 3 2 1 5 1 1 2 6 1 2 1 0 1 2 1 3 2 4 0 5 1 4 2 2 4 4 3 2 1 5 2 3 1 0 0 2 7 5 0 0 2 1 1 0 4 4 2 0 1 4 5 ...
output:
560.0000000000
result:
ok found '560.00000', expected '560.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 6272kb
input:
2 200 1 117 1 97 1 7 2 2 0 4 3 0 0 0 0 5 4 0 4 4 7 0 2 7 3 5 0 1 2 4 2 0 0 0 3 3 1 3 2 2 2 0 3 3 3 0 0 3 1 3 4 2 1 6 0 1 0 2 1 3 5 2 5 2 0 1 0 1 0 1 1 3 3 3 1 5 1 1 7 0 2 2 2 7 2 1 4 3 1 1 0 0 1 2 1 0 6 2 2 2 1 1 1 0
output:
46.0000000000
result:
ok found '46.00000', expected '46.00000', error '0.00000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 6216kb
input:
2 132 1 41 1 65 3 0 3 3 2 2 5 2 0 2 3 3 2 1 2 4 0 4 5 1 2 1 0 2 2 1 0 6 1 1 5 2 1 0 2 4 2 5 1 6 0 3 1 1 5 1 2 7 2 2 2 1 5 6 0 5 4 0 5 2 1 1 1 4 0 0
output:
49.0000000000
result:
ok found '49.00000', expected '49.00000', error '0.00000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 6216kb
input:
4 100 3 37 3 53 2 0 1 3 0 4 2 0 0 2 0 1 0 4 4 0 5 5 3 6 1 4 1 1 6 0 1 3 3 5 5 4 3 0 2 0 2 3 0 1 0 3 4 4 5 3 3 0 0 2 4 1 0 3 0 5 1 2 1 4 1 0 2 0 2 0 0 0 0 2 4 1 4 0 1 5 4 0 0 2 1 7 6 2 1 4 0 0 0 6 5 5 2 0 0 3 3 1 2 4
output:
30.0000000000
result:
ok found '30.00000', expected '30.00000', error '0.00000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
4 80 1 67 3 57 1 4 0 5 1 3 1 6 0 0 5 0 0 1 1 0 0 6 3 0 4 0 1 0 1 2 1 2 0 0 6 2 2 2 1 3 0 3 3 2 2 2 0 3 1 2 0 2 0 0 6 6 1 4 1 4 0 4 1 7 1 3 6 1 3 3 5 5 1 1 4 3 1 4 3 5 5 1 2 1
output:
25.1980390272
result:
ok found '25.19804', expected '25.19804', error '0.00000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 6196kb
input:
6 66 1 59 1 51 2 1 1 5 2 6 2 3 2 0 2 6 2 3 2 0 4 2 4 1 5 2 0 6 4 2 2 0 0 1 1 2 0 3 4 2 0 2 1 1 1 2 4 0 3 0 1 0 2 6 5 1 0 5 0 2 1 1 3 3 2 5 3 3 1 4 1 7 1 3 2 5 2 0 5 3 4 5 4 3 0 5 2 4 0 6 3 2 4 4 1 2 0 0 6 0 4 4 3
output:
17.0000000000
result:
ok found '17.00000', expected '17.00000', error '0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 6064kb
input:
6 56 1 19 5 19 1 5 5 1 1 4 4 2 4 0 0 2 0 1 4 4 2 3 3 1 5 4 4 2 4 4 3 3 0 2 0 1 1 7 2 5 0 3 1 4 1 2 6 0 5 3 1 2 0 6 3 5 2 1 1 2 4 0 1 0 0 0 3 5 1 2 5 2 0 4 5 1 6 5 2 3 2 4 5 6 4 5 7 0
output:
9.0000000000
result:
ok found '9.00000', expected '9.00000', error '0.00000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 6212kb
input:
8 50 1 31 3 7 4 3 3 1 1 3 0 1 6 0 1 4 0 0 1 5 1 3 0 3 0 4 0 0 3 3 3 5 2 3 2 1 0 5 1 4 1 5 3 7 1 2 4 3 6 0 3 1 2 5 6 0 4 5 4 2 2 1 1 7 6 2 4 3 2 3 3 0 0 0 2 3 2 0 4 1 0 1 3 3 2 0 2 5 2 6 1 0 3 1 2 1 5 2 4 1 0 2 4 2
output:
52.0831891576
result:
ok found '52.08319', expected '52.08319', error '0.00000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
8 44 3 13 7 17 1 4 1 5 2 1 0 4 1 0 5 2 0 0 4 0 1 0 4 2 5 2 2 0 0 1 1 1 1 0 2 4 1 0 3 3 4 0 1 0 0 2 2 4 4 1 1 0 4 7 2 2 4 4 4 5 0 2 0 2 4 2 6 2 4 1 3 0 4 6 2 4 7 3 2 0 6 4 1 0 1 2 5 1 2 2 3 0
output:
7.6568542495
result:
ok found '7.65685', expected '7.65685', error '0.00000'
Test #19:
score: 0
Accepted
time: 0ms
memory: 6268kb
input:
100 100 21 15 63 83 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
79.9249648108
result:
ok found '79.92496', expected '79.92496', error '0.00000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 6412kb
input:
300 300 199 221 255 3 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ...
output:
271.0777643394
result:
ok found '271.07776', expected '271.07776', error '0.00000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 6236kb
input:
20 500 5 53 1 359 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
306.0261426741
result:
ok found '306.02614', expected '306.02614', error '0.00000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 6088kb
input:
20 500 19 427 1 31 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0...
output:
485.4088798198
result:
ok found '485.40888', expected '485.40888', error '0.00000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 6080kb
input:
500 20 367 15 323 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
44.7213595500
result:
ok found '44.72136', expected '44.72136', error '0.00000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 6264kb
input:
500 20 153 13 153 5 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 ...
output:
11.0000000000
result:
ok found '11.00000', expected '11.00000', error '0.00000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 6116kb
input:
8 2000 3 269 3 341 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0...
output:
89.0000000000
result:
ok found '89.00000', expected '89.00000', error '0.00000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 6264kb
input:
2000 8 1257 5 1213 3 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0...
output:
57.0454310911
result:
ok found '57.04543', expected '57.04543', error '0.00000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 6312kb
input:
2 12000 1 11617 1 9173 116 53 123 391 240 480 746 343 689 568 312 254 30 153 642 12 269 518 172 283 460 763 193 341 92 511 22 144 6 469 487 41 380 172 24 453 520 124 734 134 291 551 519 210 127 29 533 123 101 90 245 192 633 435 343 413 710 230 574 184 53 210 121 924 75 663 221 366 836 123 609 495 65...
output:
343138.0000000000
result:
ok found '343138.00000', expected '343138.00000', error '0.00000'
Test #28:
score: 0
Accepted
time: 2ms
memory: 6348kb
input:
6 6000 5 3061 3 3761 65 23 136 112 364 257 662 118 428 60 506 687 437 45 99 195 17 61 65 107 65 147 304 957 670 368 277 153 162 471 128 22 348 181 426 113 199 223 63 10 231 507 120 2 685 411 118 919 26 61 347 446 174 193 400 349 173 64 384 235 12 558 206 256 241 124 195 179 71 13 250 211 134 595 210...
output:
95384.0028571370
result:
ok found '95384.00286', expected '95384.00286', error '0.00000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 6292kb
input:
10 4000 1 3925 5 979 0 218 7 52 96 730 484 600 592 32 53 694 81 275 458 56 124 377 217 0 750 729 17 56 372 71 170 96 280 38 87 471 475 407 594 629 595 385 670 387 589 459 433 128 319 237 386 585 237 32 672 49 387 327 871 431 384 101 513 463 24 219 985 536 363 651 135 163 11 129 744 493 614 739 733 7...
output:
384131.0027155453
result:
ok found '384131.00272', expected '384131.00272', error '0.00000'
Test #30:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
12 3000 9 775 9 2565 516 518 43 588 225 279 483 581 148 597 576 164 475 439 245 44 513 335 505 292 396 109 121 162 50 63 123 195 329 129 467 659 728 493 663 309 291 444 30 384 27 446 360 401 267 496 411 801 158 60 278 328 455 115 54 735 324 649 11 81 383 59 211 28 112 522 914 802 152 374 119 30 70 7...
output:
239411.0000000000
result:
ok found '239411.00000', expected '239411.00000', error '0.00000'
Test #31:
score: 0
Accepted
time: 1ms
memory: 6304kb
input:
16 2400 15 817 13 1343 52 588 698 118 141 30 561 198 597 445 180 791 72 65 121 64 133 79 453 206 397 468 706 868 528 36 505 289 830 95 168 479 152 428 213 113 129 133 757 66 655 409 195 663 89 135 916 257 211 192 713 791 149 311 407 427 86 746 93 66 426 653 336 631 766 705 280 29 246 236 184 113 11 ...
output:
75880.0038022676
result:
ok found '75880.00380', expected '75880.00380', error '0.00000'
Test #32:
score: 0
Accepted
time: 0ms
memory: 6288kb
input:
20 2000 5 75 9 299 254 187 385 415 5 725 163 98 108 258 833 79 605 693 184 34 731 296 330 265 777 123 14 391 82 871 228 142 443 315 95 559 338 101 262 319 58 529 97 44 277 104 120 289 542 284 56 864 176 158 248 398 36 269 520 76 312 179 63 434 577 192 740 323 918 20 88 503 413 186 826 815 121 164 22...
output:
30054.0357114390
result:
ok found '30054.03571', expected '30054.03571', error '0.00000'
Test #33:
score: 0
Accepted
time: 1ms
memory: 6192kb
input:
22 1714 13 505 3 811 291 303 418 410 452 314 468 187 305 20 91 192 355 398 960 231 453 327 521 365 267 245 204 614 508 130 231 352 714 269 12 127 341 168 480 119 270 263 378 265 240 151 224 2 633 663 166 186 692 704 344 349 804 118 115 407 417 407 664 56 450 97 81 108 622 380 319 35 736 276 540 254 ...
output:
44752.1633550901
result:
ok found '44752.16336', expected '44752.16336', error '0.00000'
Test #34:
score: 0
Accepted
time: 1ms
memory: 6312kb
input:
26 1500 25 625 5 83 423 130 183 646 327 124 135 316 45 122 245 515 348 22 214 557 77 519 190 92 420 110 520 726 40 163 177 313 528 389 107 604 151 104 278 277 506 11 207 488 812 727 192 821 72 582 424 156 649 466 512 208 625 85 325 53 5 164 273 55 169 742 311 194 194 239 688 382 602 504 385 310 19 3...
output:
68202.3688781632
result:
ok found '68202.36888', expected '68202.36888', error '0.00000'
Test #35:
score: -100
Wrong Answer
time: 1ms
memory: 6308kb
input:
28 1332 15 707 1 681 595 199 48 209 25 61 272 289 328 259 305 343 160 446 601 422 58 605 39 421 49 200 126 775 415 276 871 161 66 708 46 194 162 514 52 350 80 19 451 179 803 279 302 190 906 412 183 640 327 17 159 73 735 103 283 477 303 381 117 53 72 399 207 831 169 5 221 440 493 275 112 443 544 189 ...
output:
4008.5296461205
result:
wrong answer 1st numbers differ - expected: '3913.52965', found: '4008.52965', error = '0.02427'