Submission #60325761

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// https://github.com/Pentagon03/Algorithms
// g++ -std=c++20 -D _DEBUG
#ifdef _DEBUG
#define Pentagon03
#include<Pentagon03/debug.h>
#else
#define dbg(...)
#define dbgArr(...)
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
// #pragma GCC target("avx2", "popcnt")
#include"bits/stdc++.h"
// ext headers here: ext/pb_ds/assoc_container.hpp, tr2/dynamic_bitset
using namespace std;
string readline(char delim = '\n'){
    cin.ignore();
    string t; getline(cin, t, delim);
    return move(t);
}
// istringstream iss(s = "1 2 3 4 5"); // iss >> x;
template<typename T> istream& operator>> (istream&in, vector<T>&v){for(auto&x:v)in>>x; return in;}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

// https://github.com/Pentagon03/Algorithms
// g++ -std=c++20 -D _DEBUG
#ifdef _DEBUG
#define Pentagon03
#include<Pentagon03/debug.h>
#else
#define dbg(...)
#define dbgArr(...)
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
// #pragma GCC target("avx2", "popcnt")
#include"bits/stdc++.h"
// ext headers here: ext/pb_ds/assoc_container.hpp, tr2/dynamic_bitset
using namespace std;
string readline(char delim = '\n'){
    cin.ignore();
    string t; getline(cin, t, delim);
    return move(t);
}
// istringstream iss(s = "1 2 3 4 5"); // iss >> x;
template<typename T> istream& operator>> (istream&in, vector<T>&v){for(auto&x:v)in>>x; return in;}
template<typename T> ostream& operator<< (ostream&out, vector<T>&v){for(auto&x:v)out<<x<<' '; return out;}
auto vec(int n, auto&&... s) {
    static_assert(sizeof...(s) >= 1 and "last parameter should be initial value");
    if constexpr (sizeof...(s) == 1) return vector (n, s...);
    else return vector (n, vec(s...));
}
void assign(auto&A, auto&&n, auto&&...v){
    if constexpr(sizeof...(v) == 0) A = n;
    else for(int i=0;i<n;i++) assign(A[i], v...);
}
void append(auto&x, auto&&y){x.reserve(x.size()+y.size()), x.insert(x.end(), y.begin(), y.end());}
void addv(auto&v, auto&&...x){(v.push_back(x),...);}
template<typename T> T randint(T l, T r) {static std::mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); return std::uniform_int_distribution<T>(l,r)(gen);}
#define all(v) (v).begin(),(v).end()
#define nl '\n'
#define sp ' '
#define rep(i, n) for(int i=0;i<(n);i++)
#define rep1(i, n) for(int i=1;i<=(n);i++)
#define repr(i, a, b) for(int i=(a);i<=(b);i++)
#define repd(i, b, a) for(int i=(b);i>=(a);i--)
#define int int64_t
using ll = int64_t; using pii = pair<int,int>; int cur_tc;
constexpr int inf = (int) 1e9 + 3; constexpr ll infl = (ll) 1e18 + 3;
using ld = long double;

int32_t main(){
    cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit);
    cout<<fixed<<setprecision(16);
    int tc = 1;
    // cin >> tc;
    auto solve_tc = [&](){
        int n, m; cin >> n >> m;
        /*
        1번 뽑았을 때 
        2번 뽑았을 때
        3번 뽑았을 때 ...
        */
        // p(i): 1번 뽑았을 때 i개 나오기 위한 확률
        // dp(i): i개 뽑기 위해서 필요한 기댓값 // dp(0) = 0
        // dp(m) = 1 + (p(0)*dp(m) + p(1)*dp(m-1) + ... + (p(m)+...)*dp(0))
        // dp(m) * (1-p(0)) = 1 + (p(1)*dp(m-1) + .... (p(m)+...)*dp(0))
        vector<ld> P(n); cin >> P;
        vector<ld> p(n+1);
        p[0] = 1;
        // p(i) = (1-t) * p(i) + t * p(i-1)
        for(int i=0;i<n;i++){
            P[i] /= 100;
            vector<ld> np(n+1);
            for(int j=0;j<=i+1;j++){
                np[j] = (1-P[i]) * p[j];
                if(j) np[j] += P[i] * p[j-1];
            }
            swap(p, np);
        }
        vector<ld> dp(m+1);
        const ld div = 1 - p[0];
        for(int i=1;i<=m;i++){
            ld sum = 1;
            for(int j=1;j<=min(i-1, n); j++)
                sum += p[j] * dp[i-j];
            dp[i] = sum / div;
        }
        cout << dp[m] << nl;
    };
    for(cur_tc=1;cur_tc<=tc;cur_tc++) solve_tc();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘std::string readline(char)’:
Main.cpp:18:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
   18 |     return move(t);
      |            ~~~~^~~
Main.cpp:18:16: note: remove ‘std::move’ call

Judge Result