ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#213365 | #2053. 地雷爆炸 | STASISZHY | 100 | 3668ms | 1992kb | C++11 | 1.2kb | 2024-11-11 20:22:50 | 2024-11-11 23:03:38 |
answer
// Problem: A. 地雷爆炸
// Contest: undefined - NOIP2024训练赛 02
// URL: http://119.28.3.174/contest/1154/problem/2053
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
int n, m, q, ans;
long double s[N], dp[305][405], eps;
void dfs(int id, int now, int nd, long double f, int sum)
{
if(f < eps) return;
if(now > nd)
{
if(sum <= 400) dp[id][sum] += f;
return;
}
for(int i = 0; i < n; i ++) dfs(id, now + 1, nd, f * s[i], sum + i - 1);
}
signed main()
{
// ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// cin >> n >> m;
scanf("%d %d", &n, &m);
if(n <= 6 && m <= 6) eps = 2e-9;
else eps = 1e-6;
for(int i = 0; i < n; i ++) scanf("%LF", &s[i]);
// for(int i = 0; i < n; i ++) cout << s[i] << ' ';
dp[0][1] = 1.0;
for(int i = 1; i <= m; i ++)
{
dp[i][0] = dp[i - 1][0];
for(int j = 1; j <= 400; j ++) dfs(i, 1, j, dp[i - 1][j], j);
// cout << dp[i][0] << '\n';
}
printf("%.4Lf", dp[m][0]);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 680ms
memory: 1348kb
input:
300 20 0.00379430 0.00378180 0.00857190 0.00919620 0.00396670 0.00176760 0.00511380 0.00793840 0.005...
output:
0.0038
result:
ok single line: '0.0038'
Test #2:
score: 10
Accepted
time: 850ms
memory: 1548kb
input:
300 69 0.03642550 0.00870610 0.00174390 0.00728740 0.00917590 0.00276320 0.00788090 0.00688300 0.000...
output:
0.0367
result:
ok single line: '0.0367'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
300 1 0.02275200 0.00255280 0.00714900 0.00673530 0.00625580 0.00952860 0.00503680 0.00361520 0.0085...
output:
0.0228
result:
ok single line: '0.0228'
Test #4:
score: 10
Accepted
time: 635ms
memory: 1408kb
input:
300 34 0.01174930 0.00237960 0.00725200 0.00622610 0.00092020 0.00915390 0.00050940 0.00135760 0.006...
output:
0.0118
result:
ok single line: '0.0118'
Test #5:
score: 10
Accepted
time: 491ms
memory: 1992kb
input:
300 180 0.03276550 0.00945640 0.00095320 0.00353310 0.00647080 0.00637530 0.00059110 0.00265000 0.00...
output:
0.0331
result:
ok single line: '0.0331'
Test #6:
score: 10
Accepted
time: 491ms
memory: 1580kb
input:
300 78 0.07426740 0.00030970 0.00922200 0.00879440 0.00434000 0.00690410 0.00787240 0.00838550 0.005...
output:
0.0743
result:
ok single line: '0.0743'
Test #7:
score: 10
Accepted
time: 521ms
memory: 1356kb
input:
300 21 0.03122890 0.00933980 0.00300750 0.00424390 0.00213370 0.00940520 0.00636220 0.00227220 0.007...
output:
0.0315
result:
ok single line: '0.0315'
Test #8:
score: 10
Accepted
time: 0ms
memory: 1276kb
input:
6 4 0.64261410 0.35418080 0.00144510 0.00171790 0.00002830 0.00001380
output:
0.9831
result:
ok single line: '0.9831'
Test #9:
score: 10
Accepted
time: 0ms
memory: 1260kb
input:
6 1 0.23944990 0.51892380 0.07985400 0.07066520 0.03907530 0.05203180
output:
0.2394
result:
ok single line: '0.2394'
Test #10:
score: 10
Accepted
time: 0ms
memory: 1268kb
input:
6 3 1 0 0 0 0 0
output:
1.0000
result:
ok single line: '1.0000'