結果

問題 No.1688 Veterinarian
コンテスト
ユーザー planes
提出日時 2021-09-24 22:14:33
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,403 bytes
コンパイル時間 2,118 ms
コンパイル使用メモリ 188,812 KB
実行使用メモリ 183,712 KB
最終ジャッジ日時 2024-07-05 10:45:55
合計ジャッジ時間 9,249 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 5 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h> 
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 #define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)

struct bag{double x,y,z;};
vector<vector<vector<vector<bag>>>> memo;
vector<vector<vector<vector<bool>>>> note;
double A,B,C,N;



bag dp(double a,double b,double c,double n) {
    if(n==0) return {0,0,0};
    if(note[a][b][c][n]) return memo[a][b][c][n];
  
double k=(a+b+c)*(a+b+c-1)/2;
double x=a*(a-1)/2;
double y=b*(b-1)/2;
double z=c*(c-1)/2;

bag e={0,0,0};

if(a>1) {
   bag s=dp(a-1,b,c,n-1);
   e.x+=(s.x+1)*x/k;
   e.y+=(s.y)*x/k;
   e.z+=(s.z)*x/k;
}
if(b>1) {
    bag s=dp(a,b-1,c,n-1);
    e.y+=(s.y+1)*y/k;
    e.x+=(s.x)*y/k;
    e.z+=(s.z)*y/k;

}
if(c>1) {
    bag s=dp(a,b,c-1,n-1);
    e.x+=s.x*z/k;
    e.y+=s.y*z/k;
    e.z+=(s.z+1)*z/k;
}

double d=k-x-y-z;
if(d>0) {
    bag s=dp(a,b,c,n-1);
    e.x+=s.x*d/k;
    e.y+=s.y*d/k;
    e.z+=s.z*d/k;
}
    
note[a][b][c][n-1]=true;
memo[a][b][c][n]=e;
return e;
}

int main() {

cin>>A>>B>>C>>N;
note=vector<vector<vector<vector<bool>>>>(A+1,vector<vector<vector<bool>>> (B+1,vector<vector<bool>> (C+1,vector<bool> (N))));
memo=vector<vector<vector<vector<bag>>>> (A+1,vector<vector<vector<bag>>> (B+1,vector<vector<bag>>(C+1,vector<bag> (N))));
cout<<fixed<<setprecision(10);
bag ans=dp(A,B,C,N);

cout<<ans.x<<" "<<ans.y<<" "<<ans.z<<" "<<endl;
}
0