Submission #1092576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092576		May27_th	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	24 ms	2944 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];
pair<i64, i64> f[MAXN][MAXN];
void Maximize(pair<i64, i64> &a, pair<i64, i64> b) {
  /*
    a < b
    a.first/a.second < b.first/b.second
  */
  if (a.first * b.second < b.first * a.second) {
    a = b;
  }
}
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 i = 1; i <= N; i ++) {
    for (int j = 1; j <= N; j ++) {
      d[i][j] = (i != j ? INF : 0);
    }
  }
  for (int i = 1; i <= M; i ++) {
    int u, v; i64 w; cin >> u >> v >> w;
    d[u][v] = min(d[u][v], w);
  }
  for (int k = 1; k <= N; k ++) {
    for (int u = 1; u <= N; u ++) {
      for (int v = 1; v <= N; v ++) {
        if (d[u][k] < INF && d[k][v] < INF) {
          d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
        }
      }
    }
  }
  for (int u = 1; u <= N; u ++) {
    for (int v = 1; v <= N; v ++) {
      i64 profit = 0;
      if (u != v) {
        for (int k = 1; k <= K; k ++) {
          if (buy[u][k] != -1 && sell[v][k] != -1) {
            profit = max(profit, sell[v][k] - buy[u][k]);
          }
        }
      }
      if (d[u][v] < INF) {
        if (u == v) f[u][v] = mp(-INF, d[u][v]);
        else f[u][v] = mp(profit, d[u][v]);
      } else {
        f[u][v] = mp(0, INF);
      }
      // cout << u << " " << v << " " << f[u][v].first << " " << f[u][v].second << "\n";
    }
  }
  
  i64 profit = 0;
  for (int k = 1; k <= N; k ++) {
    for (int u = 1; u <= N; u ++) {
      for (int v = 1; v <= N; v ++) {
        if (f[u][k].second < INF && f[k][v].second < INF) {
          pair<i64, i64> cur = mp(f[u][k].first + f[k][v].first, f[u][k].second + f[k][v].second);
          // cout << u << " " << v << " " << f[u][v].first << " " << f[u][v].second << "\n";
          Maximize(f[u][v], cur);
        }
      }
    }
  }
  for (int u = 1; u <= N; u ++) {
    // cout << u << " " << f[u][u].first << " " << f[u][u].second << "\n";
    profit = max(profit, f[u][u].first / f[u][u].second);
  }
  cout << profit << "\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: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34