QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#434807#8774. Manhattan Walkucup-team3691#WA 18ms19644kbC++142.5kb2024-06-08 17:29:382024-06-08 17:29:39

Judging History

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

  • [2024-06-08 17:29:39]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:19644kb
  • [2024-06-08 17:29:38]
  • 提交

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'