Hash Code 2022

#include <bits/stdc++.h>

using namespace std;

#define long long long int

struct Person {
    string name;
    map<string, int> skills;

    Person() {}
    Person(string name): name(name) {}
};

struct Project {
    string name;
    int days, score, best_before;
    vector<pair<string, int>> roles;

    Project() {}
    Project(string name, int days, int score, int best_before):
        name(name), days(days), score(score), best_before(best_before) {}

    bool operator <(const Project &other) {
        /* if (score == other.score)
            return best_before < other.best_before;

        return score > other.score; */

        /* if (best_before == other.best_before)
            return score > other.score;

        return best_before < other.best_before; */

        if (score == other.score && days == other.days)
            return best_before < other.best_before;

        if (score == other.score)
            return days < other.days;

        return score > other.score;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;

    vector<Person> people(N);
    map<string, set<pair<int, int>>> skills;

    vector<string> all_skills;
    for (int i = 0; i < N; i++) {
        string name;
        int number_skills;
        cin >> name >> number_skills;

        people[i] = Person(name);
        for (int j = 0; j < number_skills; j++) {
            string skill; int level;
            cin >> skill >> level;
            people[i].skills[skill] = level;
            skills[skill].emplace(level, i);
            all_skills.push_back(skill);
        }
    }

    sort(all_skills.begin(), all_skills.end());
    all_skills.erase(unique(all_skills.begin(), all_skills.end()), all_skills.end());

    for (int i = 0; i < N; i++)
        for (auto skill: all_skills)
            if (!people[i].skills.count(skill))
                skills[skill].emplace(0, i);

    vector<Project> projects(M);
    for (int i = 0; i < M; i++) {
        string name;
        int days, score, best_before, number_roles;
        cin >> name >> days >> score >> best_before >> number_roles;

        projects[i] = Project(name, days, score, best_before);
        for (int j = 0; j < number_roles; j++) {
            string skill; int level;
            cin >> skill >> level;
            projects[i].roles.emplace_back(skill, level);
        }
    }

    sort(projects.begin(), projects.end());

    int time = 0, score = 0;
    vector<int> free(N, 0);

    vector<bool> done(M, false);
    vector<pair<int, vector<int>>> ans;

    for (int k = 0; k < 100; k++) {
        for (int i = 0; i < M; i++) {
            if (done[i]) continue;

            set<int> used;
            vector<int> curr;
            map<string, int> seen_skills;

            bool possible = true;
            for (auto [skill, level]: projects[i].roles) {
                int tests = 0;
                if (seen_skills[skill] >= level) level--;
                auto it = skills[skill].lower_bound(make_pair(level, 0));

                possible = false;
                while (it != skills[skill].end() && tests < 10 && !possible) {
                    if (used.count(it->second) || free[it->second] > time) it++;
                    else possible = true;
                }

                if (!possible) break;

                used.insert(it->second);
                curr.push_back(it->second);

                for (auto [person_skill, person_level]: people[it->second].skills)
                    seen_skills[person_skill] = max(seen_skills[person_skill], person_level);
            }

            if (!possible) {
                time++;
                continue;
            }

            done[i] = true;
            ans.emplace_back(i, curr);
            score += max(projects[i].score - max(time + projects[i].days - projects[i].best_before + 1, 0), 0);

            for (int j = 0; j < (int) curr.size(); j++) {
                int id = curr[j];
                free[id] = time + projects[i].days;

                auto [skill, level] = projects[i].roles[j];
                if (people[id].skills[skill] == level) {
                    skills[skill].erase(make_pair(people[id].skills[skill], id));
                    skills[skill].emplace(++people[id].skills[skill], id);
                }
            }

            time = *min(free.begin(), free.end());
        }
    }

    cout << ((int) ans.size()) << "\n";
    for (auto [project, roles]: ans) {
        cout << projects[project].name << "\n";
        for (int i = 0; i < (int) roles.size(); i++) {
            if (i) cout << " ";
            cout << people[roles[i]].name;
        }

        cout << "\n";
    }

    cout << score << "\n";
}