QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#429777 | #8774. Manhattan Walk | hos_lyric | AC ✓ | 16ms | 19676kb | C++14 | 1.9kb | 2024-06-02 20:42:14 | 2024-06-02 20:42:14 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
using Double = long double;
constexpr Double INF = 1e+20;
int M, N;
Double P;
Double dp[1010][1010];
int main() {
for (; ~scanf("%d%d%Lf", &M, &N, &P); ) {
for (int x = 0; x < M; ++x) for (int y = 0; y < N; ++y) if (x || y) {
Double a = x ? dp[x - 1][y] : INF;
Double b = y ? dp[x][y - 1] : INF;
if (a > b) {
swap(a, b);
}
// a or min{a+x, b} (0 <= x <= P)
Double &c = dp[x][y] = 0.0L;
c += a;
if (a + P <= b) {
c += a + P / 2.0L;
} else {
c += ((b - a) * ((a + b) / 2.0L) + (P - (b - a)) * b) / P;
}
c /= 2.0L;
}
printf("%.12Lf\n", dp[M - 1][N - 1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
2 3 8
output:
2.875000000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
5 5 5
output:
2.432233868874
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
1 1 1
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 13ms
memory: 19676kb
input:
1000 1000 1000000000
output:
1782317138.808375250781
result:
ok found '1782317138.8083754', expected '1782317138.8083761', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
1 4 5
output:
3.750000000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
4 1 5
output:
3.750000000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
1 1 1000000000
output:
0.000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1 2 1000000000
output:
250000000.000000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
2 1 1000000000
output:
250000000.000000000000
result:
ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 2 1
output:
0.250000000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
2 1 1
output:
0.250000000000
result:
ok found '0.2500000', expected '0.2500000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
1 10 3
output:
6.750000000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 5940kb
input:
10 1 3
output:
6.750000000000
result:
ok found '6.7500000', expected '6.7500000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 16ms
memory: 19580kb
input:
997 993 998244353
output:
1779941051.346162438393
result:
ok found '1779941051.3461626', expected '1779941051.3461628', error '0.0000000'
Test #15:
score: 0
Accepted
time: 3ms
memory: 18912kb
input:
988 313 886183312
output:
78753022570.483319237828
result:
ok found '78753022570.4833221', expected '78753022570.4833527', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 12940kb
input:
583 286 322190846
output:
8636356976.843714022078
result:
ok found '8636356976.8437138', expected '8636356976.8437138', error '0.0000000'
Test #17:
score: 0
Accepted
time: 4ms
memory: 19280kb
input:
892 468 494964816
output:
17125998682.729238955304
result:
ok found '17125998682.7292385', expected '17125998682.7292328', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 4332kb
input:
26 882 386682745
output:
78231677700.750421971083
result:
ok found '78231677700.7504272', expected '78231677700.7504883', error '0.0000000'
Test #19:
score: 0
Accepted
time: 14ms
memory: 19560kb
input:
867 926 422131798
output:
945100500.399107266334
result:
ok found '945100500.3991072', expected '945100500.3991071', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
37 68 19
output:
62.284459880159
result:
ok found '62.2844599', expected '62.2844599', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
23 90 80
output:
860.050698735791
result:
ok found '860.0506987', expected '860.0506987', error '0.0000000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5964kb
input:
43 55 85
output:
118.389267967564
result:
ok found '118.3892680', expected '118.3892680', error '0.0000000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4328kb
input:
93 66 43
output:
97.904840858751
result:
ok found '97.9048409', expected '97.9048409', error '0.0000000'
Test #24:
score: 0
Accepted
time: 1ms
memory: 6012kb
input:
78 93 30
output:
44.845452326451
result:
ok found '44.8454523', expected '44.8454523', error '0.0000000'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
9 5 481032867
output:
400507342.366738341982
result:
ok found '400507342.3667383', expected '400507342.3667384', error '0.0000000'
Test #26:
score: 0
Accepted
time: 2ms
memory: 10064kb
input:
366 73 3
output:
149.486464233096
result:
ok found '149.4864642', expected '149.4864642', error '0.0000000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
6 4 5
output:
2.894645169729
result:
ok found '2.8946452', expected '2.8946452', error '0.0000000'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
8 10 5
output:
3.397360852475
result:
ok found '3.3973609', expected '3.3973609', error '0.0000000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
10 1 7
output:
15.750000000000
result:
ok found '15.7500000', expected '15.7500000', error '0.0000000'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
10 7 10
output:
7.371646607394
result:
ok found '7.3716466', expected '7.3716466', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
2 8 1
output:
1.327106919466
result:
ok found '1.3271069', expected '1.3271069', error '0.0000000'