4-agojis-equal-day-trip

#pragma GCC optimize("Ofast", "unroll-loops")
// #pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int INF = LLONG_MAX >> 2;

void solve() {
    int N; cin >> N;

    vector<pair<int, vector<pii>>> city;
    int city_tok = 0;
    map<string, int> city_id;
    for (int i = 0; i < N; ++i) {
        string name; cin >> name;
        int days, cost; cin >> days >> cost;
        if (!city_id.count(name)) city_id[name] = city_tok++, city.eb(0, 0);
        city[city_id[name]].X += days;
        city[city_id[name]].Y.eb(cost, days);
    }
    sort(ALL(city), [](const auto &a, const auto &b) {return a.X > b.X;});
    for (auto &c : city) sort(ALL(c.Y));
    N = SZ(city);

    int max_day = 0, min_cost = INF;
    for (int i = 0; i < N; ++i) chmax(max_day, (i+1) * city[i].X);

    for (int i = 0; i < N; ++i) {
        if (max_day != (i+1) * city[i].X) continue;
        // cout << "[" << i << "]\n";
        int cost = 0;
        for (int j = 0; j <= i; ++j) {
            int D_left = city[i].X;
            for (pii &plan : city[j].Y) {
                int C = plan.X, D = plan.Y;
                cost += C * min(D, D_left);
                D_left -= D;
                if (D_left <= 0) break;
            }
        }
        chmin(min_cost, cost);
    }
    cout << max_day << " " << min_cost << "\n";
}

int32_t main() {
    fastIO();

    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }

    return 0;
}