QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#434807 | #8774. Manhattan Walk | ucup-team3691# | WA | 18ms | 19644kb | C++14 | 2.5kb | 2024-06-08 17:29:38 | 2024-06-08 17:29:39 |
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;
ld dp[DIM][DIM];
int n, m;
ld p;
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 = exp_down - exp_right;
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 = exp_right - exp_down;
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: 0ms
memory: 4004kb
input:
2 3 8
output:
2.875000000000000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
5 5 5
output:
2.432233868873881346
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3964kb
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: 18ms
memory: 19644kb
input:
1000 1000 1000000000
output:
2848359580.064675201196223497
result:
wrong answer 1st numbers differ - expected: '1782317138.8083761', found: '2848359580.0646753', error = '0.5981216'