QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197816#3518. Final StandingsMahmoudAtia#AC ✓7ms4096kbC++141.3kb2023-10-02 20:17:062023-10-02 20:17:06

Judging History

This is the latest submission verdict.

  • [2023-10-02 20:17:06]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 4096kb
  • [2023-10-02 20:17:06]
  • Submitted

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, 0, 0, 1, -1, 1};
int dj[] = {0, 1, 0, -1, -1, 0, 1, -1};

const ll oo = 1e18;
const int N = 2e5 + 5, M = 1e5 + 5, MOD = 998244353;
#define EPS 1e-9

int n, m, cnt[105], vis[105][105];
double dp[105][105], team[105], problem[105];
char c[105][105];

double solve(int id, int idx, int rem) {
    if (rem < 0) return 0;
    if (idx > m) return 1;
    double &ret = dp[idx][rem];
    if (vis[idx][rem] == id) return ret;
    vis[idx][rem] = id;
    if (c[id][idx] != '?') return ret = solve(id, idx + 1, rem);
    double prob = team[id] * problem[idx];
    ret = prob * solve(id, idx + 1, rem - 1) + (1.0 - prob) * solve(id, idx + 1, rem);
    return ret;
}

int main() {
    //  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++) cin >> team[i];
    for (int i = 1; i <= m; i++) cin >> problem[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (c[i][j] == 'X') cnt[i]++;
        }
    }
    double ans = 1;
    for (int i = 1; i < n; i++) ans *= solve(i, 1, cnt[n] - cnt[i]);
    cout << fixed << setprecision(8) << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
0.95 0.95
0.95 0.95 0.95
? ? ?
X X -
X X -

output:

0.26490811

result:

ok found '0.2649081', expected '0.2649080', error '0.0000001'

Test #2:

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

input:

2 5
0.5
0.1 0.2 0.3 0.4 0.5
? ? ? ? ?
X - - - -

output:

0.83876250

result:

ok found '0.8387625', expected '0.8387625', error '0.0000000'

Test #3:

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

input:

2 2
0.9995
0.3 0.7
? X
X -

output:

0.70015000

result:

ok found '0.7001500', expected '0.7001500', error '0.0000000'

Test #4:

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

input:

10 10
0.123 0.321 0.456 0.654 0.789 0.987 0.00001 0.999 1.0
1.0 0.0 1.0 0.0 0.333 0.333 1.0 0.0 1.0 0.0
? ? ? - ? ? ? ? ? ?
? ? ? ? ? X ? ? ? ?
? - ? - - ? X ? - ?
? X ? ? - ? ? ? ? ?
- - - - - - X - - -
? ? ? ? - ? ? ? X ?
? - - ? X X ? ? - ?
? ? ? ? ? ? ? ? - ?
- ? - ? ? ? - - - ?
- X - X - - X - ...

output:

0.43685769

result:

ok found '0.4368577', expected '0.4368577', error '0.0000000'

Test #5:

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

input:

100 100
0.689155 0.168240 0.530088 0.942735 0.768589 0.412675 0.644574 0.563462 0.328203 0.190895 0.791336 0.222512 0.689632 0.579885 0.572048 0.608610 0.092101 0.692957 0.830000 0.260008 0.176340 0.320461 0.988391 0.200428 0.802988 0.470834 0.782480 0.555422 0.215995 0.039138 0.886394 0.024748 0.69...

output:

0.01759843

result:

ok found '0.0175984', expected '0.0175984', error '0.0000000'

Test #6:

score: 0
Accepted
time: 3ms
memory: 4096kb

input:

100 100
0.739154 0.896819 0.389388 0.848565 0.594443 0.276015 0.206422 0.712795 0.365333 0.476042 0.197904 0.348222 0.578902 0.142333 0.479748 0.350042 0.919599 0.139169 0.414150 0.593798 0.916769 0.134246 0.577282 0.225321 0.099476 0.560128 0.066144 0.670162 0.754154 0.804760 0.770396 0.163091 0.55...

output:

0.91850064

result:

ok found '0.9185006', expected '0.9185006', error '0.0000000'

Test #7:

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

input:

5 10
0.242538 0.704492 0.693277 0.287680
0.803364 0.395923 0.978611 0.252482 0.742638 0.797737 0.298886 0.518122 0.712812 0.039091
? ? - X - - - ? X -
X ? X - - X ? X ? -
X - - ? - X - X - -
? X - ? X - ? X X -
- X X - - X - X X -

output:

0.72425812

result:

ok found '0.7242581', expected '0.7242581', error '0.0000000'

Test #8:

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

input:

5 10
0.967964 0.005081 0.611507 0.904663
0.299430 0.378219 0.566297 0.251130 0.315192 0.364325 0.267384 0.411746 0.750870 0.285207
- - - ? - X ? - ? X
X - X - ? - - ? ? ?
X X ? - ? - ? ? X -
- - ? - - X - ? X X
X X - - X X X X - X

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #9:

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

input:

5 10
0.905411 0.671157 0.488513 0.226860
0.430025 0.027177 0.963820 0.109811 0.653668 0.148091 0.949071 0.189172 0.918600 0.434530
X - ? X ? - X ? X X
? - ? ? - - X - ? -
X - X ? - X - - - -
X X ? ? ? - X X ? ?
- X - - - X - X X X

output:

0.03694136

result:

ok found '0.0369414', expected '0.0369414', error '0.0000000'

Test #10:

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

input:

1 4

0.2 0.3 0.4 0.5
X X - -

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

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

input:

2 1
0.6
0.9
?
-

output:

0.46000000

result:

ok found '0.4600000', expected '0.4600000', error '0.0000000'

Test #12:

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

input:

2 100
0.991921
0.998158 0.994156 0.998807 0.999717 0.990088 0.996412 0.996480 0.995090 0.993043 0.990610 0.992582 0.999043 0.990912 0.994159 0.994806 0.994192 0.990842 0.990886 0.995926 0.993143 0.993564 0.999147 0.999581 0.997420 0.993865 0.992056 0.994833 0.994969 0.991073 0.994468 0.990729 0.9926...

output:

0.00052935

result:

ok found '0.0005294', expected '0.0005293', error '0.0000000'

Test #13:

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

input:

3 100
0.608543 0.589703
0.737298 0.707906 0.778506 0.716552 0.748223 0.819207 0.834997 0.927112 0.894731 0.728533 0.830628 0.801969 0.875098 0.536811 0.710838 0.505515 0.972584 0.873987 0.878728 0.536656 0.830684 0.811442 0.515273 0.698014 0.919090 0.709101 0.994148 0.852719 0.793287 0.709344 0.8256...

output:

0.74637310

result:

ok found '0.7463731', expected '0.7463731', error '0.0000000'

Test #14:

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

input:

100 100
0.000014 0.000002 0.000006 0.000022 0.000020 0.000026 0.000004 0.000012 0.000001 0.000026 0.000004 0.000005 0.000019 0.000015 0.000028 0.000013 0.000027 0.000015 0.000021 0.000018 0.000030 0.000003 0.000015 0.000015 0.000016 0.000026 0.000022 0.000024 0.000007 0.000018 0.000013 0.000028 0.00...

output:

0.99999846

result:

ok found '0.9999985', expected '0.9999985', error '0.0000000'

Test #15:

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

input:

100 100
0.000001 0.000000 0.000000 0.000001 0.000001 0.000002 0.000000 0.000001 0.000000 0.000002 0.000000 0.000000 0.000001 0.000001 0.000002 0.000001 0.000002 0.000001 0.000001 0.000001 0.000002 0.000000 0.000001 0.000001 0.000001 0.000002 0.000001 0.000002 0.000000 0.000001 0.000001 0.000002 0.00...

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #16:

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

input:

100 100
0.863753 0.764225 0.798073 0.933327 0.920291 0.964108 0.782574 0.852625 0.758305 0.966392 0.780157 0.793895 0.905184 0.874969 0.986522 0.860725 0.976363 0.872031 0.926096 0.900000 0.995896 0.776961 0.877855 0.872115 0.884298 0.967287 0.930474 0.952758 0.805131 0.903976 0.855482 0.982786 0.75...

output:

0.99999547

result:

ok found '0.9999955', expected '0.9999955', error '0.0000000'

Test #17:

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

input:

100 100
0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421927 0.931142 0.03...

output:

0.00000000

result:

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

Test #18:

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

input:

100 100
0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421927 0.931142 0.03...

output:

0.00001201

result:

ok found '0.0000120', expected '0.0000120', error '0.0000000'

Test #19:

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

input:

100 98
0.468467 0.603265 0.455013 0.056899 0.192291 0.733306 0.681165 0.856431 0.130297 0.410500 0.033220 0.865567 0.120628 0.175581 0.620735 0.499877 0.946087 0.442901 0.905451 0.488122 0.704383 0.600001 0.983584 0.107843 0.511419 0.488460 0.537192 0.869146 0.721896 0.811033 0.220526 0.615902 0.421...

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #20:

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

input:

100 98
0.773885 0.887121 0.242746 0.707466 0.668545 0.231465 0.213497 0.106659 0.321201 0.231399 0.550282 0.240498 0.755269 0.363372 0.009735 0.564173 0.774967 0.613985 0.564827 0.463059 0.306565 0.837471 0.145482 0.998446 0.584806 0.637623 0.165856 0.549593 0.218482 0.241157 0.178319 0.222142 0.221...

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #21:

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

input:

100 100
0.048549 0.141493 0.133709 0.046293 0.042699 0.021332 0.064240 0.046280 0.110056 0.048100 0.151054 0.072674 0.001947 0.112835 0.154993 0.122797 0.112965 0.092612 0.061313 0.167494 0.029096 0.199689 0.116961 0.127525 0.033171 0.109919 0.043696 0.048231 0.035664 0.044428 0.044379 0.010996 0.12...

output:

0.00000000

result:

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

Test #22:

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

input:

100 100
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.00...

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'