QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456345 | #8774. Manhattan Walk | ucup-team2307# | WA | 21ms | 21544kb | C++20 | 1.0kb | 2024-06-27 19:08:51 | 2024-06-27 19:08:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
const int N = 2222;
double p;
double dp[N][N];
double f(int n, int m)
{
if (n > m) swap(n, m);
if (dp[n][m] > -0.1)
return dp[n][m];
if (n==1 && m==1) return 0;
if (n == 1) return f(n, m-1)+p/4;
double a = f(n, m-1);
double b = f(n-1, m);
if (a > b) swap(a, b);
double h = b-a;
double ans = 0;
ans += p/2 - (p-h)*max<double>(0, (1-h/p))/2;
return dp[n][m] = ans/2+a;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
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(10);
cout<<f(n, m)<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3888kb
input:
2 3 8
output:
2.8750000000
result:
ok found '2.8750000', expected '2.8750000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
5 5 5
output:
2.4322338689
result:
ok found '2.4322339', expected '2.4322339', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 1 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #4:
score: 0
Accepted
time: 21ms
memory: 21544kb
input:
1000 1000 1000000000
output:
1782317138.8083751202
result:
ok found '1782317138.8083751', expected '1782317138.8083761', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
1 4 5
output:
3.7500000000
result:
ok found '3.7500000', expected '3.7500000', error '0.0000000'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3900kb
input:
4 1 5
output:
0.0000000000
result:
wrong answer 1st numbers differ - expected: '3.7500000', found: '0.0000000', error = '1.0000000'