5-trip-planner

#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;}

template <typename T, typename U> bool chpmax(T &lhs, U rhs) {
    if (lhs.first < rhs.first) return lhs = rhs, 1;
    if (lhs.first == rhs.first and lhs.second > rhs.second) return lhs = rhs, 1;
    return 0;
}

const int INF = LLONG_MAX >> 2;

void solve() {
    int N, D, M; cin >> N >> D >> M;

    vector<vector<int>> Price(N+1, vector<int>(D+1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= D; ++j) cin >> Price[i][j];
    }

    vector<vector<int>> prePrice = Price;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= D; ++j) prePrice[i][j] += prePrice[i][j-1];
    }

    vector<vector<int>> Dist(N+1, vector<int>(N+1, INF));
    for (int i = 1; i <= N; ++i) Dist[i][i] = 0;
    for (int i = 0; i < M; ++i) {
        int u, v, c; cin >> u >> v >> c;
        chmin(Dist[u][v], c), chmin(Dist[v][u], c);
    }
    for (int _ : {0, 1, 2}) {
        for (int k = 1; k <= N; ++k) {
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= N; ++j) {
                    chmin(Dist[i][j], Dist[i][k] + Dist[k][j]);
                }
            }
        }
    }

    int P_discount; cin >> P_discount;
    vector<pii> discount(N+1, {D+1, 0});
    for (int i = 0; i < P_discount; ++i) {
        int Q_hotel, X_days, Y_dis; cin >> Q_hotel >> X_days >> Y_dis;
        discount[Q_hotel] = {X_days, Y_dis};
    }

    int K_cash; cin >> K_cash;
    vector<vector<int>> Cash(N+1, vector<int>(D+1, 0));
    for (int i = 0; i < K_cash; ++i) {
        int R_hotel, S_day, T_cash; cin >> R_hotel >> S_day >> T_cash;
        Cash[R_hotel][S_day] = T_cash;
    }

    vector<vector<int>> preCash = Cash;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= D; ++j) preCash[i][j] += preCash[i][j-1];
    }

    auto get_price = [&](int hotel, int dayL, int dayR) -> int {
        int dc = 0;
        if (discount[hotel].X <= dayR - dayL + 1) dc = discount[hotel].Y;
        return (prePrice[hotel][dayR] - prePrice[hotel][dayL-1]) * (100 - dc) / 100;
    };

    auto get_cash = [&](int hotel, int dayL, int dayR) -> int {
        return (preCash[hotel][dayR] - preCash[hotel][dayL-1]);
    };

    auto get_dist = [&](int st, int ed, bool free = false) -> int {
        if (free) return 0;
        return Dist[st][ed];
    };

    vector<vector<pii>> dp(D+1, vector<pii>(N+1, {-1, 0}));
    for (int i = 1; i <= N; ++i) dp[0][i] = {0, 0};
    for (int d = 1; d <= D; ++d) {
        for (int i = 1; i <= N; ++i) {
            for (int _d = 0; _d <= d; ++_d) {
                for (int j = 1; j <= N; ++j) {
                    if (Dist[i][j] == INF) continue;
                    chpmax(dp[d][i], pii{
                        dp[_d][j].X + get_cash(i, _d+1, d),
                        dp[_d][j].Y + get_price(i, _d+1, d) + get_dist(j, i, (_d == 0))
                    });
                }
            }
            // printf("dp[%d][%d] = {%d, %d}\n", d, i, dp[d][i].X, dp[d][i].Y);
        }
    }

    pii ans = {-1, 0};
    for (int i = 1; i <= N; ++i) chpmax(ans, dp[D][i]);
    cout << ans.X << " " << ans.Y << "\n";
}

int32_t main() {
    fastIO();

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

    return 0;
}