QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511100#8774. Manhattan Walkamirreza#AC ✓36ms19532kbC++172.1kb2024-08-09 16:16:202024-08-09 16:16:21

Judging History

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

  • [2024-08-09 16:16:21]
  • 评测
  • 测评结果:AC
  • 用时:36ms
  • 内存:19532kb
  • [2024-08-09 16:16:20]
  • 提交

answer


// ki bood ke goft Ghatinga?

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppiii;

// vectors and Sets:
#define vc vector
#define pb push_back
#define all(c) (c).begin(), (c).end()

// pairs
#define mp make_pair
#define fr first
#define sc second

// execution time check and Debug
#define StartEX clock_t startExeTime = clock();
#define EndEX clock_t endExeTime = clock();
#define ExTime cerr << "\nTotal Execution Time is: " << double(-double(startExeTime)+double(endExeTime)) / CLOCKS_PER_SEC;
#define debug(x) cerr << #x << " : " << x << '\n'
#define endl "\n"

// time optimization
#define Heh ios::sync_with_stdio(false);cin.tie(0);
#define Bah ios::sync_with_stdio(false);
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

// useful functions
ll pw(ll a,ll b){
  ll ret = 1;
  ll mul = a;
  while(b > 0){
	if(b&1)
	  ret = (ret * mul);
	mul = (mul * mul);
	b >>= 1;
  }
  return ret;
}
ll pw(ll a,ll b,ll mod){
  ll ret = 1;
  ll mul = a;
  while(b > 0){
	if(b&1)
	  ret = (ret * mul) % mod;
	mul = (mul * mul) % mod;
	b >>= 1;
  }
  return ret;
}

ll to_int(string s){
  ll ret = 0;
  for(int i = 0 ; i < (int)s.size() ; i++) ret = 10 * ret + s[i] - '0';
  return ret;
}

bool deq(ld a , ld b){return (abs(a-b) < 0.000001);} // 10 ^ -6

ld f(ld a , ld b , ld p){
  ld ret = 0;
  ld l = min(max((ld)0 , b - a) , p);
  ret += a * l + l * l / 2;
  ret += b * (p - l);
  ret /= p;
  return ret;
}

int main()
{
  int r , c;
  cin >> r >> c;
  ld p;
  cin >> p;
  ld dp[r][c] = {};
  for(int i = r - 1 ; i >= 0 ; i--){
    for(int j = c - 1 ; j >= 0 ; j--){
      if(i == r-1 and j == c-1) continue;
      ld a = 1e18 , b = 1e18;
      if(i != r-1) a = dp[i+1][j];
      if(j != c-1) b = dp[i][j+1];
      dp[i][j] = (ld)1/2 * f(a , b , p) + (ld)1/2 * f(b , a , p);
    }
  }
  cout << fixed << setprecision(10) << dp[0][0] << endl;
}

// ki seda kard Patinga?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3792kb

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

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

input:

1 1 1

output:

0.0000000000

result:

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

Test #4:

score: 0
Accepted
time: 36ms
memory: 19532kb

input:

1000 1000 1000000000

output:

1782317138.8083751892

result:

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

Test #5:

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

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

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

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

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

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

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

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

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

input:

10 1 3

output:

6.7500000000

result:

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

Test #14:

score: 0
Accepted
time: 36ms
memory: 19388kb

input:

997 993 998244353

output:

1779941051.3461624477

result:

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

Test #15:

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

input:

988 313 886183312

output:

78753022570.4833181873

result:

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

Test #16:

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

input:

583 286 322190846

output:

8636356976.8437139904

result:

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

Test #17:

score: 0
Accepted
time: 13ms
memory: 10324kb

input:

892 468 494964816

output:

17125998682.7292389078

result:

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

Test #18:

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

input:

26 882 386682745

output:

78231677700.7504228130

result:

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

Test #19:

score: 0
Accepted
time: 28ms
memory: 16200kb

input:

867 926 422131798

output:

945100500.3991072192

result:

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

Test #20:

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

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

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

input:

43 55 85

output:

118.3892679676

result:

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

Test #23:

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

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

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

input:

9 5 481032867

output:

400507342.3667383420

result:

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

Test #26:

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

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

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

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

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

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

input:

2 8 1

output:

1.3271069195

result:

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