VRt Contest Codeforces

#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct location {
    int x, y, d, p, l, h, num;
    location(int _x = 0, int _y = 0, int _d = 0, int _p = 0, int _l = 0, int _h = 0, int _num = 0) {
        x = _x, y = _y, d = _d, p = _p, l = _l, h = _h, num = _num;
    }
};

// list of all locations
vector <location> loc;
location base;

// magic choose
bool choose = false;

// calculate dist between 2 locations
int dist(const location & a, const location & b) {
    return abs(a.x - b.x) + abs(a.y - b.y);
}

// next best location
int find_new_location(vector <location> & one, vector <bool> & done, location & prev, int time, int m, int len, int magic, int magic2, int magic3) {
    int min_dist = 1e9, idx = -1;

    for (int i = 0; i < m; ++i) {
        // time, when workers can start
        int arrive_time = max(one[i].l, time + dist(prev, one[i]));

        // possible or not
        if (done[i] || one[i].h < one[i].d + arrive_time) continue;

        // offset towards base
        int delta = dist(one[i], base) - dist(prev, base);

        // calculate some magic ^_^
        int tmp = delta * (len - magic2) - one[i].h * magic3 / 3;
        if (choose) tmp = delta * (len - magic2) - (one[i].h - one[i].d / 15) * magic3 / 3;
        tmp /= magic;

        // refresh best values
        if (arrive_time - tmp < min_dist) {
            min_dist = arrive_time - tmp;
            idx = i;
        }
    }

    // number of next location
    return idx;
}

// main function
int f(int mg, int mg2, int mg3, bool debug = true) {
    // total sum
    int sum = 0;

    // group of workers
    for (int workers = 1; workers <= 7; ++workers) {
        // answer
        string answer_line;
        vector <string> ans;

        // list of locations with loc[i].p == workers
        vector <location> one;
        for (int i = 0; i < (int) loc.size(); ++i) {
            if (loc[i].p == workers) one.push_back(loc[i]);
        }

        // all, left, completed localions
        int m = one.size();
        int left = m;
        vector <bool> done(m, false);

        while (left > 0) {
            location prev = base;

            // find start_time
            int idx = find_new_location(one, done, prev, 0, m, 0, mg, mg2, mg3);
            int start_time = 0;

            // check
            if (idx != -1) start_time = one[idx].l - dist(base, one[idx]);
            else break;

            // current time
            int time = start_time;

            // sum and asnwer per one pass
            int local_sum = 0;
            vector <string> local_ans;

            // answer
            if (!debug) {
                answer_line = "start " + to_string(time) + " 1";
                local_ans.push_back(answer_line);
            }

            // length of paths
            int len = 0;
            while (true) {
                // find new location
                int idx = find_new_location(one, done, prev, time, m, len, mg, mg2, mg3);
                if (idx == -1) break;

                done[idx] = true;
                left--;
                location job = one[idx];

                // working
                int arrive_time = max(job.l, time + dist(prev, job));

                // answer
                if (!debug) {
                    answer_line = "arrive " + to_string(arrive_time) + " " + to_string(job.num);
                    local_ans.push_back(answer_line);
                    answer_line = "work " + to_string(arrive_time) + " " + to_string(arrive_time + job.d) + " " + to_string(job.num);
                    local_ans.push_back(answer_line);
                }

                // profit
                local_sum += job.d * job.p * (job.p + 5);

                // update
                prev = job;
                time = job.d + arrive_time;
                len++;
            }

            // answer
            if (!debug) {
                answer_line = "arrive " + to_string(time + dist(prev, base)) + " 1";
                local_ans.push_back(answer_line);
                answer_line = "end";
                local_ans.push_back(answer_line);
            }

            // lost
            local_sum -= (time - start_time) * workers;
            local_sum -= dist(prev, base) * workers;
            local_sum -= 240 * workers;

            // Only (profit > lost) deals
            if (local_sum > 0) {
                sum += local_sum;

                // print answer
                if (!debug) {
                    for (int k = 0; k < workers; ++k) {
                        for (auto e : local_ans) {
                            cout << e << "\n";
                        }
                    }
                }
            }
        }
    }

    return sum;
}

int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;

    int nil;
    cin >> base.x >> base.y >> nil >> nil >> nil >> nil;

    // locations
    loc.resize(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> loc[i].x >> loc[i].y >> loc[i].d >> loc[i].p >> loc[i].l >> loc[i].h;
        loc[i].num = i + 2;
    }

    // calculate magic values
    int magic = -1, magic2 = -1, magic3 = -1, max_magic = 0;
    bool choose_val = false;
    for (int mg2= -44; mg2 <= -23; ++mg2) {
        for (int mg = 55; mg <= 83; ++mg) {
            for (int mg3 = 9; mg3 <= 14; ++mg3) {
                int total = f(mg, mg2, mg3);

                // for "magic choose"
                int total2 = 0;
                bool use_choose = false;
                if (n < 1000) {
                    choose = true;
                    total2 = f(mg, mg2, mg3);
                    choose = false;
                    if (total2 > total) {
                        total = total2;
                        use_choose = true;
                    }
                }

                if (total > max_magic) {
                    max_magic = total;
                    magic = mg;
                    magic2 = mg2;
                    magic3 = mg3;
                    choose_val = use_choose;
                }
            }
        }
    }
    choose = choose_val;

    //cout << "total sum = " << max_magic << endl;
    //cout << "choose_val = " << choose << endl;
    //cout << "magic, magic2, magic3 = " << magic << ' ' << magic2 << ' ' << magic3 << endl;

    // Get answer
    f(magic, magic2, magic3, false);
}