fork download
copy 
  1. /// Google Code Jam 2017 Round 1C Problem A
  2.  
  3. /// Bismillahir Rahmanir Rahim
  4. /// S. M. Shakir Ahsan Romeo ( Pure_Protea, #theromeo421, Cosmos_Freak )
  5. /// CSE Discipline, Khulna University, Khulna
  6. /// Monirampur, Jessore.
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10.  
  11. typedef long long lng;
  12. typedef vector < int >  vi;
  13. typedef vector < lng >  vl;
  14. typedef pair < int, int >  pii;
  15. typedef vector < pii >  vpii;
  16.  
  17. const int inf = 1 << 30;
  18. const long long linf = 1LL << 62;
  19. const double PI = acos(-1.0), dinf = (double)(1LL << 62), eps = (double)(1e-9);
  20.  
  21. double distance(double x1, double y1, double x2, double y2)
  22. {
  23.     x1 -= x2;
  24.     y1 -= y2;
  25.     return sqrt(x1 * x1 + y1 * y1);
  26. }
  27. long long POW(long long b, long long p)
  28. {
  29.     if(p == 0)
  30.         return 1;
  31.     long long t = POW(b, p >> 1);
  32.     if(p & 1)
  33.         return t * t * b;
  34.     return t * t;
  35. }
  36. long long bigmod(long long b, long long p, long long m)
  37. {
  38.     if(p == 0)
  39.         return 1;
  40.     long long t = POW(b, p >> 1) % m;
  41.     t = (t * t) % m;
  42.     if(p & 1)
  43.         t = (t * b) % m;
  44.     return t;
  45. }
  46. inline int getint()
  47. {
  48.     int x;
  49.     scanf("%d", &x);
  50.     return x;
  51. }
  52. inline long long getlng()
  53. {
  54.     long long x;
  55.     scanf("%lld", &x);
  56.     return x;
  57. }
  58.  
  59. lng gcd(lng a, lng b)
  60. {
  61.     return !b ? a : gcd(b, a % b);
  62. }
  63.  
  64. lng lcm(lng a, lng b)
  65. {
  66.     return (a / gcd(a, b)) * b;
  67. }
  68.  
  69. int dx4[] = {-1, 0, 1, 0};
  70. int dy4[] = {0, 1, 0, -1};
  71. int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  72. int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  73.  
  74. #define theromeo421 main()
  75. #define segtree int lft = node << 1, rgt = lft | 1, mid = (b + e) >> 1;
  76. #define mem(x, y) memset(x, y, sizeof x);
  77. #define II getint()
  78. #define LL getlng()
  79. #define sz(x) ((int)x.size())
  80. #define sqr(x) ((x) * (x))
  81. #define max3(a,b,c) max(a, max(b,c))
  82. #define min3(a,b,c) min(a, min(b,c))
  83. #define pr1(x) cout << x << endl
  84. #define pr2(x,y) cout << x << ' ' << y << endl
  85. #define pr3(x,y,z) cout << x << ' ' << y << ' ' << z << endl
  86. #define pr4(a,b,c,d) cout << a << ' ' << b << ' ' << c << ' ' << d << endl
  87. #define rep(i, n) for(int i = 0; i < n; ++i)
  88. #define rep1(i, n) for(int i = 1; i <= n; ++i)
  89. #define repab(i, a, b) for(int i = a; i <= b; ++i)
  90. #define repstl(it, x) for(auto it = x.begin(); it != x.end(); it++)
  91. #define repbstl(it, x) for(auto it = x.rbegin(); it != x.rend(); it++)
  92. #define forch(it, x) for(auto it : x)
  93. #define pb push_back
  94. #define all(x) x.begin(), x.end()
  95. #define xx first
  96. #define yy second
  97. #define dbg(x) cerr << #x << " :  " << x << endl;
  98. #define read(a) freopen(a, "r", stdin);
  99. #define write(a) freopen(a, "w", stdout);
  100. #define prv(v) rep(i, v.size()) cout << v[i] << " \n"[i + 1 == v.size()];
  101. #define prmp(x) repstl(it, x) pr2(it->xx, it->yy)
  102. #define pause int ppause; cin >> ppause;
  103. #define pf printf
  104. #define sf scanf
  105.  
  106.  
  107.  
  108. void IO()
  109. {
  110.     read("A-large.in");
  111.     write("out.txt");
  112. }
  113.  
  114. void solve();
  115.  
  116. int theromeo421
  117. {
  118.     //IO();
  119.  
  120.     int T = II;
  121.     cerr << T << " Case(s) need to be solved" << endl;
  122.     rep1(cas, T)
  123.     {
  124.         printf("Case #%d: ", cas);
  125.         solve();
  126.         cerr << "Case " << cas << " solved" << endl;
  127.     }
  128.     cerr << "Done" << endl;
  129.     return 0;
  130. }
  131.  
  132. const int N = 1010;
  133. int n, k;
  134. bool vis[N][N];
  135. double dp[N][N];
  136.  
  137. struct data
  138. {
  139.     double r = 0, h = 0;
  140.     data() {}
  141.     data(double a, double b)
  142.     {
  143.         r = a;
  144.         h = b;
  145.     }
  146.     bool operator < (const data& DT) const
  147.     {
  148.         return r > DT.r;
  149.     }
  150. };
  151.  
  152. vector < data > D;
  153.  
  154. double call(int i, int K)
  155. {
  156.     if(i > n)
  157.     {
  158.         if(K == k)
  159.             return 0;
  160.         return -dinf;
  161.     }
  162.     if(vis[i][K])
  163.         return dp[i][K];
  164.     vis[i][K] = true;
  165.     if(K == 0)
  166.     {
  167.         double p1 = PI * D[i].r * D[i].r + 2.0 * PI * D[i].r * D[i].h + call(i + 1, 1);
  168.         double p2 = call(i + 1, 0);
  169.         return dp[i][K] = max(p1, p2);
  170.     }
  171.     else
  172.     {
  173.         if(K < k)
  174.         {
  175.             double p1 = 2.0 * PI * D[i].r * D[i].h + call(i + 1, K + 1);
  176.             double p2 = call(i + 1, K);
  177.             return dp[i][K] = max(p1, p2);
  178.         }
  179.         else
  180.         {
  181.             return dp[i][K] = 0;
  182.         }
  183.     }
  184. }
  185.  
  186. void solve()
  187. {
  188.     n = II;
  189.     k = II;
  190.     mem(vis, false);
  191.     D.resize(n + 1);
  192.     rep1(i, n)
  193.     {
  194.         double a, b;
  195.         cin >> a >> b;
  196.         D[i] = data(a, b);
  197.     }
  198.     sort(D.begin() + 1, D.end());
  199.     printf("%0.10f\n", call(1, 0));
  200. }
  201.  
Success #stdin #stdout #stderr 0s 24208KB
comments (?)
stdin
copy 
4
2 1
100 20
200 10
2 2
100 20
200 10
3 2
100 10
100 10
100 10
4 2
9 3
7 1
10 1
8 4
stdout
copy 
Case #1: 138230.0767579509
Case #2: 150796.4473723101
Case #3: 43982.2971502571
Case #4: 625.1769380644
stderr
copy 
4 Case(s) need to be solved
Case 1 solved
Case 2 solved
Case 3 solved
Case 4 solved
Done
https://ideone.com/TyrKDk
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!