Submission #531467

#	Time	Username	Problem	Language	Result	Execution time	Memory
531467		Alex_tz307	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	127 ms	1300 KiB

merchant

#include <bits/stdc++.h>

using namespace std;

const int64_t INF = 1e18L;

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void minSelf(int64_t &x, int64_t y) {
  if (y < x) {
    x = y;
  }
}

void FloydWarshall(vector<vector<int64_t>> &d) {
  int n = d.size() - 1;
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        minSelf(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
}

void testCase() {
  int n, m, k;
  cin >> n >> m >> k;
  vector<vector<int>> b(n + 1, vector<int>(k + 1)), s(n + 1, vector<int>(k + 1));
  vector<vector<int64_t>> d(n + 1, vector<int64_t>(n + 1, INF));
  for (int u = 1; u <= n; ++u) {
    for (int i = 1; i <= k; ++i) {
      cin >> b[u][i] >> s[u][i];
    }
  }
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    d[u][v] = w;
  }
  FloydWarshall(d);
  vector<vector<int>> profit(n + 1, vector<int>(n + 1));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int p = 1; p <= k; ++p) {
        if (b[i][p] != -1 && s[j][p] != -1) {
          maxSelf(profit[i][j], s[j][p] - b[i][p]);
        }
      }
    }
  }
  int l = 1, r = 1e9;
  while (l <= r) {
    int mid = (l + r) / 2;
    vector<vector<int64_t>> dp(n + 1, vector<int64_t>(n + 1));
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        dp[i][j] = (int64_t)mid * min(d[i][j], INF / mid) - profit[i][j];
      }
    }
    FloydWarshall(dp);
    bool ok = false;
    for (int v = 1; v <= n; ++v) {
      if (dp[v][v] <= 0) {
        ok = true;
      }
    }
    if (ok) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  cout << r << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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