Submission #3945765

Source Code Expand

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

LL N;
std::vector<long double>p;
std::vector<std::vector<long double>>memo;

long double dp(LL i, LL j)
{
	if (i == N)
	{
		if (j > i - j) return 1.;
		else return 0.;
	}
	if (memo[i][j] != -1) return memo[i][j];
	auto res1 = dp(i + 1, j + 1)*p[i], res2 = dp(i + 1, j)*(1. - p[i]);
	return memo[i][j] = res1 + res2;
}

int main()
{
	in >> N;
	p.resize(N);
	rep(i, N) in >> p[i];

	memo.resize(N);
	rep(i, memo.size()) memo[i].resize(N, -1.);
	out << std::fixed << std::setprecision(10);
	out << dp(0, 0) << std::endl;
}

Submission Info

Submission Time
Task I - Coins
User Bwambocos
Language C++14 (GCC 5.4.1)
Score 100
Code Size 684 Byte
Status AC
Exec Time 286 ms
Memory 141184 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 33
Set Name Test Cases
All 0_00, 0_01, 0_02, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29
Case Name Status Exec Time Memory
0_00 AC 1 ms 256 KiB
0_01 AC 1 ms 256 KiB
0_02 AC 1 ms 256 KiB
1_00 AC 1 ms 256 KiB
1_01 AC 1 ms 256 KiB
1_02 AC 1 ms 256 KiB
1_03 AC 263 ms 141184 KiB
1_04 AC 261 ms 141184 KiB
1_05 AC 265 ms 141184 KiB
1_06 AC 283 ms 139776 KiB
1_07 AC 262 ms 140416 KiB
1_08 AC 254 ms 137728 KiB
1_09 AC 277 ms 138752 KiB
1_10 AC 254 ms 137728 KiB
1_11 AC 274 ms 136448 KiB
1_12 AC 260 ms 130944 KiB
1_13 AC 283 ms 140544 KiB
1_14 AC 255 ms 137728 KiB
1_15 AC 275 ms 137600 KiB
1_16 AC 264 ms 139264 KiB
1_17 AC 283 ms 140928 KiB
1_18 AC 276 ms 137984 KiB
1_19 AC 277 ms 137984 KiB
1_20 AC 274 ms 136448 KiB
1_21 AC 266 ms 139264 KiB
1_22 AC 265 ms 139264 KiB
1_23 AC 286 ms 139008 KiB
1_24 AC 255 ms 138496 KiB
1_25 AC 276 ms 138368 KiB
1_26 AC 248 ms 132992 KiB
1_27 AC 281 ms 140544 KiB
1_28 AC 252 ms 136320 KiB
1_29 AC 253 ms 136704 KiB