Submission #1117986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117986		duckindog	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	57 ms	3672 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

const int N = 100 + 10,
          K = 1000 + 10;
const long long MAX = 1'000'000'000'000'000'000 + 10;

int n, m, k;
int buy[N][K], sell[N][K];
vector<pair<int, int>> ad[N];

long long dist[N][N], profit[N][N];
long long f[N][N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> k;
  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= k; ++j) cin >> buy[i][j] >> sell[i][j];
  }
  for (int i = 1; i <= m; ++i) { 
    int u, v, w; cin >> u >> v >> w;
    ad[u].push_back({v, w});
  }

  memset(dist, 14, sizeof dist);
  for (int u = 1; u <= n; ++u) { 
    for (const auto& [v, w] : ad[u]) dist[u][v] = w;
  }
  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 x = 1; x <= k; ++x) { 
    for (int i = 1; i <= n; ++i) { 
      for (int j = 1; j <= n; ++j) { 
        if (buy[i][x] == -1 || sell[j][x] == -1) continue;
        profit[i][j] = max(profit[i][j], 1ll * sell[j][x] - buy[i][x]);
      }
    }
  }

  auto chk = [&](int expectedValue) { 
    memset(f, -14, sizeof f);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) 
        if (i != j) f[i][j] = profit[i][j] - min(dist[i][j], MAX / expectedValue) * expectedValue;
    }

    for (int k = 1; k <= n; ++k) { 
      for (int i = 1; i <= n; ++i) { 
        for (int j = 1; j <= n; ++j) f[i][j] = max(f[i][j], f[i][k] + f[k][j]);
      }
    }
    
    for (int i = 1; i <= n; ++i) if (f[i][i] >= 0) return true;
    return false;
  };

  int le = 1, ri = 1'000'000'000, ret = 0;
  while (le <= ri) { 
    int mid = (le + ri) >> 1;
    if (chk(mid)) le = (ret = mid) + 1;
    else ri = mid - 1;
  }

  cout << ret << "\n";
}

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