QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#198524#3518. Final StandingsAnwar#AC ✓1ms4028kbC++201.5kb2023-10-03 14:35:182023-10-03 14:35:18

Judging History

This is the latest submission verdict.

  • [2023-10-03 14:35:18]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4028kb
  • [2023-10-03 14:35:18]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 3, MOD = 998244353;//1e9 + 7;

int32_t main() {

    cin.tie(0);cin.sync_with_stdio(0);
    cout.tie(0);cout.sync_with_stdio(0);

    int n ,m;
    cin >> n >> m;

    double s[n] , d[m] ;

    for (int i = 0; i < n - 1; ++i) {
        cin >> s[i] ;
    }

    for (int i = 0; i < m; ++i) {
        cin >> d[i] ;
    }

    char a[n][m] ;

    for (int i = 0; i < n; ++i) {

        for (int j = 0; j < m; ++j) {
            cin >> a[i][j] ;
        }
    }

    int c =0 ;
    for(int j =0 ; j < m ; j++) c+= (a[n-1][j] == 'X');

    double ans = 1;

    for(int i =0 ; i < n-1; i++)
    {
        double dp[m+1][m+1] ;

        memset(dp , 0 ,sizeof dp);

        int be = 0;
        for (int j = 0; j < m; ++j) {
            be += (a[i][j] == 'X') ;
        }

        for(int cc = 0 ; cc <= c-be; cc++) dp[m][cc] =1;

        for(int j = m-1 ; j >= 0 ; j--)
        {
            for(int cc = 0; cc <= c - be ; cc++)
            {
                double & ret = dp[j][cc] ;

                if(a[i][j] != '?')
                {
                    ret = dp[j+1][cc] ;
                    continue;
                }

                ret = (1 - s[i]*d[j])* dp[j+1][cc] ;

                ret += s[i]*d[j]*dp[j+1][cc+1] ;
            }
        }

        ans *= dp[0][0];
    }

    cout << fixed << setprecision(11) << ans ;

    return 0;
}

詳細信息

Test #1:

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

input:

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

output:

0.26490810938

result:

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

Test #2:

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

input:

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

output:

0.83876250000

result:

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

Test #3:

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

input:

2 2
0.9995
0.3 0.7
? X
X -

output:

0.70015000000

result:

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

Test #4:

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

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.43685769243

result:

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

Test #5:

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

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.01759843086

result:

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

Test #6:

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

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.91850064484

result:

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

Test #7:

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

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.72425812482

result:

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

Test #8:

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

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.00000000000

result:

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

Test #9:

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

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.03694136018

result:

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

Test #10:

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

input:

1 4

0.2 0.3 0.4 0.5
X X - -

output:

1.00000000000

result:

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

Test #11:

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

input:

2 1
0.6
0.9
?
-

output:

0.46000000000

result:

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

Test #12:

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

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.00052934893

result:

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

Test #13:

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

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.74637310301

result:

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

Test #14:

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

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.99999845814

result:

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

Test #15:

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

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:

0.99999999511

result:

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

Test #16:

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

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.99999546604

result:

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

Test #17:

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

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.00000000000

result:

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

Test #18:

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

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.00001200605

result:

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

Test #19:

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

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.00000000000

result:

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

Test #20:

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

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.00000000000

result:

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

Test #21:

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

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.00000000000

result:

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

Test #22:

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

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.00000000000

result:

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