QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#434838 | #8774. Manhattan Walk | ucup-team3691# | WA | 82ms | 19732kb | C++14 | 3.0kb | 2024-06-08 17:36:48 | 2024-06-08 17:36:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
string to_string(const string &s) {
return '"' + s + '"';
}
string to_string(bool b) {
return b ? "true" : "false";
}
template <typename A, typename B>
string to_string(const pair<A, B> &p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename T>
string to_string(const T &v) {
string s = "{";
bool first = true;
for (const auto &it : v) {
if (!first)
s += ", ";
else
first = false;
s += to_string(it);
}
return s += "}";
}
void debug_out() {
cerr << endl;
}
template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
cerr << to_string(first) << " ";
debug_out(rest...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto startTime = high_resolution_clock::now();
int get_time() {
auto stopTime = chrono::high_resolution_clock::now();
auto duration = duration_cast<milliseconds>(stopTime - startTime);
return duration.count(); // in ms
}
const int DIM = 1001;
const ld step = 1e-6;
ld dp[DIM][DIM];
int n, m;
ld p;
ld eval(ld dif, ld e1, ld e2) {
return (dif * e1 + (p - dif) * e2 + dif * dif * 0.5) / p;
}
ld ternary_search(ld e1, ld e2) {
int steps = 64;
ld st = 0, dr = p;
while (steps--) {
ld mid = (st + dr) / 2.0;
if (eval(mid, e1, e2) < eval(mid + step, e1, e2))
dr = mid;
else
st = mid;
}
return (st + dr) / 2;
}
ld f(int r, int c) {
if(r == n && c == m) return 0;
if(r > n || c > m) return 1e20;
if (dp[r][c] >= -0.1)
return dp[r][c];
ld exp_down = f(r + 1, c);
ld exp_right = f(r, c + 1);
ld point_down;
if(exp_right + p * 0.5 < exp_down) point_down = exp_right + p * 0.5;
else if(exp_down < exp_right) point_down = exp_down;
else {
ld dif = ternary_search(exp_right, exp_down);
point_down = (dif * exp_right + (p - dif) * exp_down + dif * dif * 0.5) / p;
}
ld point_right;
if(exp_down + p * 0.5 < exp_right) point_right = exp_down + p * 0.5;
else if(exp_right < exp_down) point_right = exp_right;
else {
ld dif = ternary_search(exp_down, exp_right);
point_right = (dif * exp_down + (p - dif) * exp_right + dif * dif * 0.5) / p;
}
ld exp = 0.5 * (point_down + point_right);
dp[r][c] = exp;
return exp;
}
void solve() {
cin >> n >> m >> p;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
dp[i][j] = -1;
cout << fixed << setprecision(18) << f(1, 1) << endl;
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3872kb
input:
2 3 8
output:
2.875000000000007812
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 5 5
output:
2.432233868873927961
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
1 1 1
output:
0.000000000000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: -100
Wrong Answer
time: 82ms
memory: 19732kb
input:
1000 1000 1000000000
output:
2848372767.909780647605657578
result:
wrong answer 1st numbers differ - expected: '1782317138.8083761', found: '2848372767.9097805', error = '0.5981290'