Submission #1100511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100511		vjudge1	Kitchen (BOI19_kitchen)	C++17	0 / 100	8 ms	8428 KiB

kitchen

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const long long INF = 1e18;
struct dinic {
	const static bool SCALING = false; // scaling = EV log(max C) with larger constant
	long long lim = 1;

	struct edge {
		int u, v;
		long long cap, flow;
	};

	int n, s, t;
	vector<int> level, ptr;
	vector<edge> e;
	vector<vector<int>> g;

	dinic(int _n) : n(_n), level(_n), ptr(_n), g(_n) {
		e.clear();
		for(int i = 0; i < n; ++i) {
			ptr[i] = 0;
			g[i].clear();
		}
	}

	void add_edge(int u, int v, long long c) {
		g[u].push_back((int)e.size());
		e.push_back({u, v, c, 0});
		g[v].push_back((int)e.size());
		e.push_back({v, u, 0, 0});
	}

	long long get_max_flow(int _s, int _t) {
		s = _s, t = _t;
		long long flow = 0;
		for(lim = SCALING ? (1ll << 59) : 1; lim > 0; lim >>= 1) {
			while(1) {
				if(!bfs()) break;
				fill(ptr.begin(), ptr.end(), 0);
				while(long long pushed = dfs(s, INF))
					flow += pushed;
			}
		}
		return flow;
	}

	private:
	bool bfs() {
		queue<int> q;
		q.push(s);
		fill(level.begin(), level.end(), -1);
		level[s] = 0;
		while(!q.empty()) {
			int u = q.front();
			q.pop();
			for(int id : g[u]) {
				if(e[id].cap - e[id].flow < lim)
					continue;
				if(level[e[id].v] != -1)
					continue;
				level[e[id].v] = level[u] + 1;
				q.push(e[id].v);
			}
		}
		return level[t] != -1;
	}

	long long dfs(int u, long long flow) {
		if(!flow)
			return 0;
		if(u == t)
			return flow;
		for(; ptr[u] < (int)g[u].size(); ++ptr[u]) {
			int id = g[u][ptr[u]], to = e[id].v;
			if(level[to] != level[u] + 1)
				continue;
			long long pushed = dfs(to, min(flow, e[id].cap - e[id].flow));
			if(pushed) {
				e[id].flow += pushed;
				e[id ^ 1].flow -= pushed;
				return pushed;
			}
		}
		return 0;
	}
};

const int maxn = 305;
int n, m, k;
int a[maxn], b[maxn];

void solve() {
  cin >> m >> n >> k;
  int sum = 0;
  for(int i = 1; i <= m; ++i) {
    cin >> b[i];
    if(b[i] < k) {
      cout << "Impossible";
      return;
    }
  }
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
  }
  sum -= m * k;
  if(sum < 0) {
    cout << "Impossible";
    return;
  }
  dinic flow(n + m + 3);
  for(int i = 1; i <= n; ++i) {
    flow.add_edge(n + m + 1, i, a[i]);
  }
  int total = 0;
  for(int i = 1; i <= m; ++i) {
    flow.add_edge(n + i, n + m + 2, k);
    total += b[i] - k;
  }
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
      flow.add_edge(i, n + j, 1);
    }
  }
  int max_flow = flow.get_max_flow(n + m + 1, n + m + 2);
  debug(max_flow);
  if(max_flow == m * k and sum >= total) {
    cout << sum - total;
  }
  else {
    cout << "Impossible";
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28