Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <vector>
  7. #include <string>
  8. #include <fstream>
  9. #include <bitset>
  10. #include <queue>
  11. #include <stack>
  12. #include <deque>
  13. #include <complex>
  14. #include <iomanip>
  15. #include <cstdio>
  16. #include <cstring>
  17. #include <random>
  18. #include <cassert>
  19. #include <functional>
  20.  
  21. using namespace std;
  22. #define all(x) (x).begin(), (x).end()
  23.  
  24. #define int long long
  25.  
  26. const int INF = 1e18;
  27. int n, m;
  28. int w, h[500];
  29. int V[500];
  30. int x[500];
  31. int y[500];
  32. int hw;
  33.  
  34. int a[500][500];
  35. int b[500][500];
  36.  
  37. int v[100000], u[100000];
  38. int f[100000], c[100000];
  39. vector<int> graph[100000];
  40. int cnt;
  41. int pnt[100000], dist[100000];
  42. int T;
  43. int Go, send;
  44.  
  45. int dfs(int v, int want)
  46. {
  47. if (want == 0 || v == T) return want;
  48. for (; pnt[v] < graph[v].size(); pnt[v]++)
  49. {
  50. int e = graph[v][pnt[v]];
  51. int w = u[e];
  52. if (dist[w] == dist[v] + 1 && f[e] + Go <= c[e])
  53. {
  54. int go = dfs(w, min(c[e] - f[e], want));
  55. if (go > 0)
  56. {
  57. f[e] += go;
  58. f[e ^ 1] -= go;
  59. return go;
  60. }
  61. }
  62. }
  63. return 0;
  64. }
  65.  
  66. int q[100000];
  67. int qsz;
  68.  
  69. bool step()
  70. {
  71. for (int i = 0; i <= T; i++) dist[i] = 1e9, pnt[i] = 0;
  72. dist[0] = 0;
  73. qsz = 1;
  74. for (int i = 0; i < qsz; i++)
  75. {
  76. int x = q[i];
  77. for (auto e : graph[x])
  78. {
  79. int y = u[e];
  80. if (dist[x] + 1 < dist[y] && f[e] + Go <= c[e])
  81. {
  82. dist[y] = dist[x] + 1;
  83. q[qsz++] = y;
  84. }
  85. }
  86. }
  87. int t = 0;
  88. int F = 0;
  89. while (F = dfs(0, INF))
  90. {
  91. t = 1;
  92. send -= F;
  93. }
  94. return t;
  95. }
  96.  
  97. signed main()
  98. {
  99. ios_base::sync_with_stdio(false);
  100. cin.tie(0), cout.tie(0);
  101. double in;
  102. cin >> n >> m >> in;
  103. w = in * 1000000;
  104. cin >> in;
  105. T = n + m + 1;
  106. for (int i = 0; i < m; i++)
  107. {
  108. cin >> in;
  109. V[i] = in * 1000000000000LL;
  110. }
  111. for (int i = 1; i < n; i++)
  112. {
  113. cin >> in;
  114. y[i] = in * 1000000;
  115. }
  116. for (int i = 0; i < n; i++)
  117. {
  118. x[i] = y[i + 1] - y[i];
  119. }
  120. x[n - 1] = w - y[n - 1];
  121. for (int i = 0; i < n; i++)
  122. {
  123. for (int j = 0; j < m; j++)
  124. {
  125. cin >> in;
  126. a[i][j] = in * 1000000000000LL;
  127. h[i] = h[i] + (a[i][j] / x[i]);
  128. V[j] -= a[i][j];
  129. }
  130. }
  131. for (int i = 0; i < n; i++)
  132. {
  133. for (int j = 0; j < m; j++)
  134. {
  135. cin >> in;
  136. b[i][j] = in * 1000000000000LL;
  137. }
  138. }
  139. int mx = 0, mn = 1e18;
  140. for (int i = 0; i < n; i++) mx = max(mx, h[i]);
  141. for (int i = 0; i < n; i++) mn = min(mn, h[i]);
  142. int l = 0, r = mx - mn;
  143. int it = 23;
  144. while (it--)
  145. {
  146. int mid = (l + r) >> 1;
  147. int H = mx - mid;
  148. while (cnt > 0)
  149. {
  150. c[cnt - 1] = 0, f[cnt - 1] = 0;
  151. cnt--;
  152. }
  153. for (int j = 0; j < 500; j++) graph[j].clear();
  154. send = 0;
  155. for (int j = 0; j < m; j++)
  156. {
  157. graph[0].emplace_back(cnt);
  158. v[cnt] = 0, u[cnt] = j + 1, c[cnt] = V[j];
  159. cnt++;
  160. graph[j + 1].emplace_back(cnt);
  161. v[cnt] = j + 1, u[cnt] = 0;
  162. cnt++;
  163. }
  164. for (int j = 0; j < n; j++)
  165. {
  166. graph[m + 1 + j].emplace_back(cnt);
  167. v[cnt] = m + 1 + j, u[cnt] = m + n + 1, c[cnt] = max(0LL, (H - h[j]) * x[j]);
  168. send += c[cnt];
  169. cnt++;
  170. graph[m + n + 1].emplace_back(cnt);
  171. v[cnt] = m + n + 1, u[cnt] = m + 1 + j;
  172. cnt++;
  173. }
  174. for (int i = 0; i < n; i++)
  175. {
  176. for (int j = 0; j < m; j++)
  177. {
  178. graph[j + 1].emplace_back(cnt);
  179. v[cnt] = j + 1, u[cnt] = m + i + 1, c[cnt] = b[i][j] - a[i][j];
  180. ++cnt;
  181. graph[m + i + 1].emplace_back(cnt);
  182. v[cnt] = m + i + 1, u[cnt] = j + 1;
  183. ++cnt;
  184. }
  185. }
  186. Go = 1;
  187. for (;;)
  188. {
  189. while (step()) ;
  190. Go = Go >> 1;
  191. if (Go == 0) break;
  192. if (send == 0) break;
  193. }
  194. if (send == 0)
  195. r = mid;
  196. else
  197. l = mid;
  198. }
  199. printf("%.9f", r / 1000000.0);
  200. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement