Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cstdio>
- #include <cstring>
- #include <deque>
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- typedef long long i64;
- const int MAX_N = 1005;
- vector<int> tasks[MAX_N];
- bool done[MAX_N];
- int n;
- int m;
- bool IsAllDone() {
- for (int i = 1; i <= m; i++) {
- if (!done[i]) {
- return false;
- }
- }
- return true;
- }
- vector<int> gr[MAX_N];
- int mt[MAX_N];
- bool us[MAX_N];
- bool Kuhn(int u) {
- if (us[u]) {
- return false;
- }
- us[u] = true;
- for (int i = 0; i < gr[u].size(); i++) {
- int v = gr[u][i];
- if (mt[v] == -1 || Kuhn(mt[v])) {
- mt[v] = u;
- return true;
- }
- }
- return false;
- }
- int Solve() {
- for (int i = 1; i <= n; i++) {
- gr[i].clear();
- for (int j = 0; j < tasks[i].size(); j++) {
- int task = tasks[i][j];
- if (done[task]) {
- continue;
- }
- gr[i].push_back(task);
- }
- }
- memset(mt, -1, sizeof(mt));
- for (int i = 1; i <= n; i++) {
- memset(us, 0, sizeof(us));
- Kuhn(i);
- }
- int res = 0;
- for (int i = 1; i <= m; i++) {
- if (mt[i] != -1) {
- res++;
- done[i] = true;
- }
- }
- return res;
- }
- int main() {
- #ifdef NOVACO
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen("contest.in", "r", stdin);
- freopen("contest.out", "w", stdout);
- #endif
- int t;
- int l;
- cin >> n >> m >> t >> l;
- for (int i = 1; i <= n; i++) {
- int k;
- cin >> k;
- for (int j = 0; j < k; j++) {
- int a;
- cin >> a;
- tasks[i].push_back(a);
- }
- }
- int dirt = 0;
- int res = 0;
- for (int i = 0; i < t / l; i++) {
- if (IsAllDone()) {
- break;
- }
- int solved = Solve();
- res += solved;
- dirt += solved * l * (i + 1);
- }
- cout << res << " " << dirt << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement