Submission #62883

#	Time	Username	Problem	Language	Result	Execution time	Memory
62883		fallingstar	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	155 ms	1692 KiB

merchant

#include <iostream>
#include <algorithm>

#define long long long

using namespace std;

const int N = 100 + 2;
const int K = 1000 + 2;
const long INF = 1e18;

struct TFrac
{
    long num, den;
    double val() { return den != 0 ? (double) num / den : 0; }
};
auto maxDen = [](TFrac a, TFrac b) { return a.val() < b.val() || (a.val() == b.val() && a.den < b.den); };
auto minDen = [](TFrac a, TFrac b) { return a.val() < b.val() || (a.val() == b.val() && a.den > b.den); };

struct TState
{
    TFrac f[2];
    TFrac& operator[] (int id) { return f[id]; }
    TFrac operator[] (int id) const { return f[id]; }
    TState() {}
    TState(const TFrac &frac): f{frac, frac} {}
    TState(const TFrac &f0, const TFrac &f1): f{f0, f1} {}
};
TState operator + (const TState &a, const TState &b)
{
    TFrac p[4];
    double maxVal = 0;
    for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j)
        {
            p[i * 2 + j] = {a[i].num + b[j].num, a[i].den + b[j].den};
            maxVal = max(maxVal, p[i * 2 + j].val());
        }
    return {*max_element(p, p + 4, minDen), *max_element(p, p + 4, maxDen)};
}

int n, m, k;
int priceBuy[N][K];
int priceSell[N][K];
long dist[N][N];
TState f[N][N];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < k * 2; ++j)
            if (j & 1) cin >> priceSell[i][j / 2];
            else cin >> priceBuy[i][j / 2];

    for (int i = 1; i <= n; ++i)
    {
        fill(dist[i] + 1, dist[i] + 1 + n, INF);
        dist[i][i] = 0;
    }

    for (int i = 0; i < m; ++i)
    {
        int u, v, w; cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], (long) w);
    }

    // Floyd-Warshall algorithm
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            if (i == j || dist[i][j] == INF) continue;
            long num = 0, den = dist[i][j];
            for (int l = 0; l < k; ++l)
                if (priceBuy[i][l] != -1 && priceBuy[i][l] < priceSell[j][l])
                {
                    num = max(num, (long) priceSell[j][l] - priceBuy[i][l]);
                }
            f[i][j] = TFrac{num, den};
        }

    for (int l = 1; l <= n; ++l)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (dist[i][l] != INF && dist[l][j] != INF)
                {
                    TState new_state = f[i][l] + f[l][j];
                    TFrac p[4] = {f[i][j][0], f[i][j][1], new_state[0], new_state[1]};
                    f[i][j] = TState {*max_element(p, p + 4, minDen), *max_element(p, p + 4, maxDen)};
                }

    long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, (long) f[i][i][0].val());

//    for (int l = 0; l < k; ++l)
//        for (int j = 2; j <= n; ++j)
//            if (priceSell[j][l] > priceBuy[1][l] && priceBuy[1][l] != -1 && dist[1][j] != INF && dist[j][1] != INF)
//                ans = max(ans, (priceSell[j][l] - priceBuy[1][l]) / (dist[1][j] + dist[j][1]));

    cout << ans;
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34