QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131591 | #4687. Weather Report | PetroTarnavskyi# | AC ✓ | 12ms | 4056kb | C++17 | 1.5kb | 2023-07-27 18:16:42 | 2023-07-27 18:16:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define FILL(a, b) memset(a, b, sizeof(a))
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long double db;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
int n;
db p[4];
cin >> n;
FOR(i, 0, 4) {
cin >> p[i];
}
vector<LL> fact(n + 1);
vector<db> pw[4];
FOR(i, 0, 4) {
pw[i].resize(n + 1);
pw[i][0] = 1;
FOR(j, 1, n + 1) {
pw[i][j] = pw[i][j - 1] * p[i];
}
}
fact[0] = 1;
FOR(i, 1, n + 1) {
fact[i] = fact[i - 1] * i;
}
map<db, LL> mp;
FOR(c0, 0, n + 1) {
FOR(c1, 0, n + 1 - c0) {
FOR(c2, 0, n + 1 - c0 - c1) {
int c3 = n - c0 - c1 - c2;
mp[pw[0][c0] * pw[1][c1] * pw[2][c2] * pw[3][c3]] += fact[n] / (fact[c0] * fact[c1] * fact[c2] * fact[c3]);
}
}
}
db ans = 0;
while (!mp.empty()) {
auto [val, cnt] = *mp.begin();
mp.erase(mp.begin());
if (cnt > 1) {
mp[2 * val] += cnt / 2;
ans += 2 * (cnt / 2) * val;
}
if (cnt % 2 == 1) {
if (mp.empty()) {
break;
}
auto [val2, cnt2] = *mp.begin();
mp[val + val2]++;
ans += val + val2;
mp[val2]--;
}
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
2 0.9 0.049999 0.05 0.000001
output:
1.4575099500
result:
ok found '1.45751', expected '1.45751', error '0.00000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
20 0.25 0.25 0.25 0.25
output:
40.0000000000
result:
ok found '40.00000', expected '40.00000', error '0.00000'
Test #3:
score: 0
Accepted
time: 10ms
memory: 4036kb
input:
19 0.5 0.3 0.08615 0.11385
output:
32.0000551029
result:
ok found '32.00006', expected '32.00006', error '0.00000'
Test #4:
score: 0
Accepted
time: 7ms
memory: 3896kb
input:
19 0.255 0.265 0.235 0.245
output:
37.9943446614
result:
ok found '37.99434', expected '37.99435', error '0.00000'
Test #5:
score: 0
Accepted
time: 11ms
memory: 4056kb
input:
20 0.066667 0.133333 0.266667 0.533333
output:
32.8488848021
result:
ok found '32.84888', expected '32.84889', error '0.00000'
Test #6:
score: 0
Accepted
time: 9ms
memory: 4008kb
input:
20 0.27 0.26 0.24 0.23
output:
39.9700244231
result:
ok found '39.97002', expected '39.97002', error '0.00000'
Test #7:
score: 0
Accepted
time: 3ms
memory: 3984kb
input:
20 0.5 0.2 0.175 0.125
output:
35.6177332358
result:
ok found '35.61773', expected '35.61773', error '0.00000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3844kb
input:
2 0.9 0.05 0.049999 0.000001
output:
1.4575099500
result:
ok found '1.45751', expected '1.45751', error '0.00000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
3 0.25 0.25 0.25 0.25
output:
6.0000000000
result:
ok found '6.00000', expected '6.00000', error '0.00000'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
9 0.25 0.25 0.25 0.25
output:
18.0000000000
result:
ok found '18.00000', expected '18.00000', error '0.00000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
9 0.1 0.4 0.3 0.2
output:
16.6459855790
result:
ok found '16.64599', expected '16.64599', error '0.00000'
Test #12:
score: 0
Accepted
time: 12ms
memory: 3820kb
input:
20 0.56 0.1 0.01 0.33
output:
27.9269671936
result:
ok found '27.92697', expected '27.92697', error '0.00000'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
1 0.5 0.25 0.125 0.125
output:
1.7500000000
result:
ok found '1.75000', expected '1.75000', error '0.00000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
2 0.5 0.25 0.125 0.125
output:
3.5000000000
result:
ok found '3.50000', expected '3.50000', error '0.00000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
3 0.5 0.25 0.125 0.125
output:
5.2500000000
result:
ok found '5.25000', expected '5.25000', error '0.00000'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
11 0.5 0.25 0.125 0.125
output:
19.2500000000
result:
ok found '19.25000', expected '19.25000', error '0.00000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3736kb
input:
1 0.403 0.199 0.199 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
1 0.199 0.403 0.199 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
1 0.199 0.199 0.403 0.199
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
1 0.199 0.199 0.199 0.403
output:
1.9950000000
result:
ok found '1.99500', expected '1.99500', error '0.00000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
4 0.4 0.25 0.24 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
4 0.25 0.4 0.24 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
4 0.25 0.24 0.4 0.11
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
4 0.25 0.24 0.11 0.4
output:
7.5251345700
result:
ok found '7.52513', expected '7.52513', error '0.00000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 0.0001 0.0002 0.00034 0.99936
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
4 0.99936 0.00034 0.0002 0.0001
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
4 0.00034 0.99936 0.0002 0.0001
output:
1.0089885151
result:
ok found '1.00899', expected '1.00899', error '0.00000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
20 0.000001 0.999997 0.000001 0.000001
output:
1.0003570084
result:
ok found '1.00036', expected '1.00036', error '0.00000'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
15 0.000001 0.000001 0.999997 0.000001
output:
1.0002520045
result:
ok found '1.00025', expected '1.00025', error '0.00000'
Test #30:
score: 0
Accepted
time: 3ms
memory: 3800kb
input:
18 0.01 0.345 0.345 0.3
output:
29.6750587434
result:
ok found '29.67506', expected '29.67506', error '0.00000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
17 0.13 0.35 0.13 0.39
output:
31.0568361587
result:
ok found '31.05684', expected '31.05684', error '0.00000'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
20 0.14 0.33 0.14 0.39
output:
37.0670968886
result:
ok found '37.06710', expected '37.06710', error '0.00000'
Test #33:
score: 0
Accepted
time: 3ms
memory: 3884kb
input:
20 0.125001 0.25 0.5 0.124999
output:
35.0000000000
result:
ok found '35.00000', expected '35.00000', error '0.00000'
Test #34:
score: 0
Accepted
time: 3ms
memory: 3700kb
input:
20 0.01 0.34503 0.34503 0.29994
output:
32.9672035253
result:
ok found '32.96720', expected '32.96720', error '0.00000'
Test #35:
score: 0
Accepted
time: 2ms
memory: 3848kb
input:
20 0.4 0.2 0.3 0.1
output:
36.9592971671
result:
ok found '36.95930', expected '36.95930', error '0.00000'
Test #36:
score: 0
Accepted
time: 4ms
memory: 3900kb
input:
20 0.01 0.02 0.03 0.94
output:
8.3247096881
result:
ok found '8.32471', expected '8.32471', error '0.00000'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
20 0.991 0.003 0.003 0.003
output:
2.1213818217
result:
ok found '2.12138', expected '2.12138', error '0.00000'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
20 0.495 0.005 0.495 0.005
output:
21.6754013648
result:
ok found '21.67540', expected '21.67540', error '0.00000'
Test #39:
score: 0
Accepted
time: 11ms
memory: 3812kb
input:
20 0.492 0.008 0.493 0.007
output:
22.3229281448
result:
ok found '22.32293', expected '22.32293', error '0.00000'
Test #40:
score: 0
Accepted
time: 12ms
memory: 3940kb
input:
20 0.032 0.051 0.023 0.894
output:
12.9856549695
result:
ok found '12.98565', expected '12.98565', error '0.00000'
Test #41:
score: 0
Accepted
time: 12ms
memory: 3816kb
input:
20 0.002 0.01 0.09 0.898
output:
10.7619687926
result:
ok found '10.76197', expected '10.76197', error '0.00000'
Test #42:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
20 0.91 0.03 0.03 0.03
output:
11.6424469039
result:
ok found '11.64245', expected '11.64245', error '0.00000'