Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <set>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #include <string>
- #include <fstream>
- #include <bitset>
- #include <queue>
- #include <stack>
- #include <deque>
- #include <complex>
- #include <iomanip>
- #include <cstdio>
- #include <cstring>
- #include <random>
- #include <cassert>
- #include <functional>
- using namespace std;
- #define all(x) (x).begin(), (x).end()
- #define int long long
- const int INF = 1e18;
- int n, m;
- int w, h[500];
- int V[500];
- int x[500];
- int y[500];
- int hw;
- int a[500][500];
- int b[500][500];
- int v[100000], u[100000];
- int f[100000], c[100000];
- vector<int> graph[100000];
- int cnt;
- int pnt[100000], dist[100000];
- int T;
- int Go, send;
- int dfs(int v, int want)
- {
- if (want == 0 || v == T) return want;
- for (; pnt[v] < graph[v].size(); pnt[v]++)
- {
- int e = graph[v][pnt[v]];
- int w = u[e];
- if (dist[w] == dist[v] + 1 && f[e] + Go <= c[e])
- {
- int go = dfs(w, min(c[e] - f[e], want));
- if (go > 0)
- {
- f[e] += go;
- f[e ^ 1] -= go;
- return go;
- }
- }
- }
- return 0;
- }
- int q[100000];
- int qsz;
- bool step()
- {
- for (int i = 0; i <= T; i++) dist[i] = 1e9, pnt[i] = 0;
- dist[0] = 0;
- qsz = 1;
- for (int i = 0; i < qsz; i++)
- {
- int x = q[i];
- for (auto e : graph[x])
- {
- int y = u[e];
- if (dist[x] + 1 < dist[y] && f[e] + Go <= c[e])
- {
- dist[y] = dist[x] + 1;
- q[qsz++] = y;
- }
- }
- }
- int t = 0;
- int F = 0;
- while (F = dfs(0, INF))
- {
- t = 1;
- send -= F;
- }
- return t;
- }
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- double in;
- cin >> n >> m >> in;
- w = in * 1000000;
- cin >> in;
- T = n + m + 1;
- for (int i = 0; i < m; i++)
- {
- cin >> in;
- V[i] = in * 1000000000000LL;
- }
- for (int i = 1; i < n; i++)
- {
- cin >> in;
- y[i] = in * 1000000;
- }
- for (int i = 0; i < n; i++)
- {
- x[i] = y[i + 1] - y[i];
- }
- x[n - 1] = w - y[n - 1];
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- cin >> in;
- a[i][j] = in * 1000000000000LL;
- h[i] = h[i] + (a[i][j] / x[i]);
- V[j] -= a[i][j];
- }
- }
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- cin >> in;
- b[i][j] = in * 1000000000000LL;
- }
- }
- int mx = 0, mn = 1e18;
- for (int i = 0; i < n; i++) mx = max(mx, h[i]);
- for (int i = 0; i < n; i++) mn = min(mn, h[i]);
- int l = 0, r = mx - mn;
- int it = 23;
- while (it--)
- {
- int mid = (l + r) >> 1;
- int H = mx - mid;
- while (cnt > 0)
- {
- c[cnt - 1] = 0, f[cnt - 1] = 0;
- cnt--;
- }
- for (int j = 0; j < 500; j++) graph[j].clear();
- send = 0;
- for (int j = 0; j < m; j++)
- {
- graph[0].emplace_back(cnt);
- v[cnt] = 0, u[cnt] = j + 1, c[cnt] = V[j];
- cnt++;
- graph[j + 1].emplace_back(cnt);
- v[cnt] = j + 1, u[cnt] = 0;
- cnt++;
- }
- for (int j = 0; j < n; j++)
- {
- graph[m + 1 + j].emplace_back(cnt);
- v[cnt] = m + 1 + j, u[cnt] = m + n + 1, c[cnt] = max(0LL, (H - h[j]) * x[j]);
- send += c[cnt];
- cnt++;
- graph[m + n + 1].emplace_back(cnt);
- v[cnt] = m + n + 1, u[cnt] = m + 1 + j;
- cnt++;
- }
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < m; j++)
- {
- graph[j + 1].emplace_back(cnt);
- v[cnt] = j + 1, u[cnt] = m + i + 1, c[cnt] = b[i][j] - a[i][j];
- ++cnt;
- graph[m + i + 1].emplace_back(cnt);
- v[cnt] = m + i + 1, u[cnt] = j + 1;
- ++cnt;
- }
- }
- Go = 1;
- for (;;)
- {
- while (step()) ;
- Go = Go >> 1;
- if (Go == 0) break;
- if (send == 0) break;
- }
- if (send == 0)
- r = mid;
- else
- l = mid;
- }
- printf("%.9f", r / 1000000.0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement