結果
問題 | No.1688 Veterinarian |
ユーザー |
![]() |
提出日時 | 2021-09-24 23:56:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,394 bytes |
コンパイル時間 | 1,890 ms |
コンパイル使用メモリ | 187,708 KB |
実行使用メモリ | 183,584 KB |
最終ジャッジ日時 | 2024-07-05 11:38:57 |
合計ジャッジ時間 | 7,612 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 5 TLE * 1 -- * 8 |
ソースコード
#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; }