Submission #1261216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261216		LucaLucaM	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	42 ms	2112 KiB

merchant

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

#define int ll

const ll INF = 3e18;

signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n, m, K;
  std::cin >> n >> m >> K;

  std::vector<std::vector<int>> buy(n, std::vector<int>(K));
  std::vector<std::vector<int>> sell(n, std::vector<int>(K));
  
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < K; j++) {
      std::cin >> buy[i][j] >> sell[i][j];
      if (buy[i][j] == -1) {
        buy[i][j] = +INF;
      }
      if (sell[i][j] == -1) {
        sell[i][j] = -INF;
      }
    }
  }
  
  std::vector<std::vector<int>> dist(n, std::vector<int>(n, (int) +INF));

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

  for (int k = 0; k < n; k++) {
    for (int u = 0; u < n; u++) {
      for (int v = 0; v < n; v++) {
        dist[u][v] = std::min(dist[u][v], dist[u][k] + dist[k][v]);
      }
    }
  }

  std::vector<std::vector<int>> profit(n, std::vector<int>(n, 0));

  for (int u = 0; u < n; u++) {
    for (int v = 0; v < n; v++) {
      for (int i = 0; i < K; i++) {
        profit[u][v] = 0;
        profit[u][v] = std::max(profit[u][v], sell[v][i] - buy[u][i]);
      }
    }
  }
  
  auto check = [&](int mid) {
    std::vector<std::vector<ll>> cost(n, std::vector<ll>(n, +INF));
    for (int u = 0; u < n; u++) {
      for (int v = 0; v < n; v++) {
        if (dist[u][v] < +INF) {
          cost[u][v] = (ll) dist[u][v] * mid - profit[u][v];
        } else {
          cost[u][v] = +INF;
        }
      }
    }
    for (int k = 0; k < n; k++) {
      for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
          cost[u][v] = std::min(cost[u][v], cost[u][k] + cost[k][v]);
          cost[u][v] = std::max(cost[u][v], -INF);
        }
      }
    }

    for (int u = 0; u < n; u++) {
      for (int v = 0; v < n; v++) {
        if (cost[u][v] + cost[v][u] <= 0) {
          return true;
        }
      }
    }
    return false;
  };

  int l = 0, r = 1e9;
  while (l < r) {
    int mid = (l + r + 1) / 2;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  std::cout << r;

  return 0;
}

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