Submission #968899

#	Time	Username	Problem	Language	Result	Execution time	Memory
968899		kilkuwu	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	75 ms	4320 KiB

merchant

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int N, M, K;
  std::cin >> N >> M >> K;
  constexpr int64_t inf = 1e18;
  int64_t B[N][K], S[N][K], d[N][N], p[N][N], cost[N][N];

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      d[i][j] = inf;
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < K; j++) {
      std::cin >> B[i][j] >> S[i][j];
    }
  }

  for (int i = 0; i < M; i++) {
    int u, v, c;
    std::cin >> u >> v >> c;
    --u, --v;
    d[u][v] = std::min(d[u][v], (int64_t) c);
  }

  for (int k = 0; k < N; k++) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  dbg("done floyd")

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      p[i][j] = 0; // not doing shit
      for (int k = 0; k < K; k++) {
        if (B[i][k] != -1 && S[j][k] != -1) {
          p[i][j] = std::max(p[i][j], S[j][k] - B[i][k]);
        }
      }
    }
  }

  dbg("done profit");

  int lb = 0, rb = 1e9;
  while (lb < rb) {
    int mb = (lb + rb + 1) / 2;
    dbg(mb);

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        cost[i][j] = std::min(inf / mb, d[i][j]) * mb - p[i][j];
      }
    }

    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k][j]);
        }
      }
    }

    bool good = 0;
    for (int i = 0; i < N; i++) {
      good |= cost[i][i] <= 0;
    }

    if (good) {
      lb = mb;
    } else {
      rb = mb - 1;
    }
  }

  std::cout << lb << nl;

  // profit / time >= mid 
  // profit - time * mid >= 0 
  // a neg loop 




}

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