Advertisement
juaniisuar

TLE 49

Oct 18th, 2018
356
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.64 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <cmath>
  6. #include <map>
  7. #include <cstring>
  8. #include <iomanip>
  9.  
  10. #pragma GCC optimize("Ofast")
  11. #pragma GCC optimize("unroll-loops")
  12.  
  13. #define forr(i,x,n) for(int i=(x); i<int(n); i++)
  14. #define forn(i,n) forr(i,0,n)
  15.  
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19. typedef double real;
  20.  
  21. const ll MAXN = 2005;
  22. const real INF = 1e9;
  23.  
  24. ll N;
  25. vector<real> C(MAXN);
  26. real LSUM[MAXN];
  27. real RSUM[MAXN];
  28.  
  29. real DP[MAXN][MAXN][2];
  30.  
  31. real f(int s, int e, int b){
  32. if(DP[s][e][b] >= 0) return DP[s][e][b];
  33.  
  34. real ans = INF;
  35. real denom = LSUM[s-1] + RSUM[e];
  36.  
  37. if(b == 0){
  38. if(s > 0) ans = min(ans, (1 - C[s-1]/denom) * ( f(s-1, e, 0) + 1 ) + 1 * C[s-1]/denom);
  39. if(e < 2*N) ans = min(ans, ( f(s, e+1, 1) + (e-s+1) ) * (1 - C[e]/denom) + (e-s+1) * C[e]/denom);
  40. }else{
  41. if(s > 0) ans = min(ans, (1 - C[s-1]/denom) * ( f(s-1, e, 0) + (e-s+1) ) + (e-s+1) * C[s-1]/denom);
  42. if(e < 2*N) ans = min(ans, ( f(s, e+1, 1) + 1 ) * (1 - C[e]/denom) + C[e]/denom);
  43. }
  44.  
  45. return DP[s][e][b] = ans;
  46. }
  47.  
  48. int main(){
  49. ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  50. //freopen("in.txt", "r", stdin);
  51.  
  52. cin>>N;
  53.  
  54. forn(i,2*N+1) forn(j,2*N+1) forn(b,2) DP[i][j][b] = -1;
  55. forn(b,2) DP[0][2*N][b] = 0;
  56.  
  57. forn(i, 2*N) cin >> C[i];
  58. LSUM[0] = C[0];
  59. forr(i, 1, 2*N)
  60. LSUM[i] = LSUM[i-1] + C[i];
  61.  
  62. RSUM[2*N-1] = C[2*N-1];
  63. for(int i = 2*N-2; i >=0; i--)
  64. RSUM[i] = RSUM[i+1] + C[i];
  65.  
  66. cout << fixed << showpoint << setprecision(6) << f(N, N, 0) << endl;
  67.  
  68. return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement