Submission #1092575

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092575		May27_th	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	75 ms	4272 KiB

merchant

// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
  
using namespace std;
  
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
  
const int MAXN = 102;
const int MAXK = 1003;
const i64 INF = LLONG_MAX/2;
int N, M, K;
i64 d[MAXN][MAXN], buy[MAXN][MAXK], sell[MAXN][MAXK], p[MAXN][MAXN], f[MAXN][MAXN];
void floyd(i64 g[MAXN][MAXN]) {
  for (int k = 1; k <= N; k ++) {
    for (int u = 1; u <= N; u ++) {
      for (int v = 1; v <= N; v ++) {
        g[u][v] = min(g[u][v], g[u][k] + g[k][v]);
      }
    }
  }
}
void Solve(void) {  
  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 u = 1; u <= N; u ++) {
    for (int v = 1; v <= N; v ++) {
      p[u][v] = 0;
      d[u][v] = INF;
    }
  }
  for (int i = 1; i <= M; i ++) {
    int u, v; i64 w; cin >> u >> v >> w;
    d[u][v] = min(d[u][v], w);
  }
  floyd(d);
  for (int u = 1; u <= N; u ++) {
    for (int v = 1; v <= N; v ++) {
      for (int k = 1; k <= K; k ++) {
        if (sell[v][k] != -1 && buy[u][k] != -1) {
          p[u][v] = max(p[u][v], sell[v][k] - buy[u][k]);
        }
      }
    }
  } 

  // check if there is a non-negative cycle
  auto check = [&](i64 rat) {
    for (int u = 1; u <= N; u ++) {
      for (int v = 1; v <= N; v ++) {
        // Reverse to find non-positve cycle
        f[u][v] = rat * min(INF/rat, d[u][v]) - p[u][v];
      }
    }
    floyd(f);
    for (int i = 1; i <= N; i ++) if (f[i][i] <= 0) return true;
    return false;
  };

  i64 l = 1, h = 1e18; 
  while (l <= h) {
    i64 mid = (l + h)/2;
    if (check(mid)) l = mid + 1;
    else h = mid - 1;
  }
  cout << h << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(10);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

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