QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#451279#8774. Manhattan Walkhenryx#AC ✓8ms11128kbC++172.1kb2024-06-23 02:29:492024-06-23 02:29:49

Judging History

你现在查看的是最新测评结果

  • [2024-06-23 02:29:49]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:11128kb
  • [2024-06-23 02:29:49]
  • 提交

answer

#include <bits/stdc++.h>
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
#define int ll
#define ln '\n'
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define repb(i, a, b) for(int i = (a); i >= (b); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
//#define pb push_back
#define f first
#define s second
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef long double ld;
const int S = int(2e7)+10;
const ll INF = ll(1e18)+10;
const double EPS = 1e-8;
const double PI = 3.141592653589793238;
const int magic = 330LL;
int MOD = int(1e9)+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
template <typename T> void print(T &v) { cout << sz(v) << endl; trav(x, v) cerr << x << " "; cerr << endl; }
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }

void solve() {
    int n, m, p;
    cin >> n >> m >> p;
    n++; m++;
    vector<vd> f(n, vd(m,0));
    rep(i, 1, n)
        f[i][1] = (i-1)/4.0;
    rep(i, 1, m)
        f[1][i] = (i-1)/4.0;
    rep(i, 2, n)
        rep(j, 2, m) {
            double a = min(f[i-1][j], f[i][j-1]), b = max(f[i-1][j], f[i][j-1]);
            f[i][j] = 0.5*a + 0.5*(b-a >= 1 ? a+0.5 : (b-a)*((a+b)/2) + (1-b+a)*b);
        }
    cout << fixed << setprecision(10);
    cout << f[n-1][m-1]*p << endl;
}



int32_t main(){
    fastio;
    #ifdef LOCAL
    freopen("stuff.in", "r", stdin);
    #endif
    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: 3824kb

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: 3780kb

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: 3992kb

input:

1 1 1

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

score: 0
Accepted
time: 8ms
memory: 11128kb

input:

1000 1000 1000000000

output:

1782317138.8083746433

result:

ok found '1782317138.8083746', expected '1782317138.8083761', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

1 4 5

output:

3.7500000000

result:

ok found '3.7500000', expected '3.7500000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

4 1 5

output:

3.7500000000

result:

ok found '3.7500000', expected '3.7500000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

1 1 1000000000

output:

0.0000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

1 2 1000000000

output:

250000000.0000000000

result:

ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

2 1 1000000000

output:

250000000.0000000000

result:

ok found '250000000.0000000', expected '250000000.0000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

1 2 1

output:

0.2500000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

2 1 1

output:

0.2500000000

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

1 10 3

output:

6.7500000000

result:

ok found '6.7500000', expected '6.7500000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

10 1 3

output:

6.7500000000

result:

ok found '6.7500000', expected '6.7500000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 7ms
memory: 11012kb

input:

997 993 998244353

output:

1779941051.3461623192

result:

ok found '1779941051.3461623', expected '1779941051.3461628', error '0.0000000'

Test #15:

score: 0
Accepted
time: 4ms
memory: 5908kb

input:

988 313 886183312

output:

78753022570.4833374023

result:

ok found '78753022570.4833374', expected '78753022570.4833527', error '0.0000000'

Test #16:

score: 0
Accepted
time: 2ms
memory: 4416kb

input:

583 286 322190846

output:

8636356976.8437118530

result:

ok found '8636356976.8437119', expected '8636356976.8437138', error '0.0000000'

Test #17:

score: 0
Accepted
time: 5ms
memory: 6532kb

input:

892 468 494964816

output:

17125998682.7292461395

result:

ok found '17125998682.7292461', expected '17125998682.7292328', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3972kb

input:

26 882 386682745

output:

78231677700.7504577637

result:

ok found '78231677700.7504578', expected '78231677700.7504883', error '0.0000000'

Test #19:

score: 0
Accepted
time: 4ms
memory: 9348kb

input:

867 926 422131798

output:

945100500.3991076946

result:

ok found '945100500.3991077', expected '945100500.3991071', error '0.0000000'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

37 68 19

output:

62.2844598802

result:

ok found '62.2844599', expected '62.2844599', error '0.0000000'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

23 90 80

output:

860.0506987358

result:

ok found '860.0506987', expected '860.0506987', error '0.0000000'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

43 55 85

output:

118.3892679676

result:

ok found '118.3892680', expected '118.3892680', error '0.0000000'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

93 66 43

output:

97.9048408588

result:

ok found '97.9048409', expected '97.9048409', error '0.0000000'

Test #24:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

78 93 30

output:

44.8454523265

result:

ok found '44.8454523', expected '44.8454523', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

9 5 481032867

output:

400507342.3667383790

result:

ok found '400507342.3667384', expected '400507342.3667384', error '0.0000000'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

366 73 3

output:

149.4864642331

result:

ok found '149.4864642', expected '149.4864642', error '0.0000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

6 4 5

output:

2.8946451697

result:

ok found '2.8946452', expected '2.8946452', error '0.0000000'

Test #28:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

8 10 5

output:

3.3973608525

result:

ok found '3.3973609', expected '3.3973609', error '0.0000000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

10 1 7

output:

15.7500000000

result:

ok found '15.7500000', expected '15.7500000', error '0.0000000'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10 7 10

output:

7.3716466074

result:

ok found '7.3716466', expected '7.3716466', error '0.0000000'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

2 8 1

output:

1.3271069195

result:

ok found '1.3271069', expected '1.3271069', error '0.0000000'