Submission #906105

#	Time	Username	Problem	Language	Result	Execution time	Memory
906105		nguyentunglam	Travelling Merchant (APIO17_merchant)	C++17	100 / 100	98 ms	3624 KiB

merchant

#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 110, M = 1e3 + 10;

int n, m, K;

int x[N * N], y[N * N], z[N * N];

long long f[N][N], g[N][N];

int cost[N][N];

int s[N][M], b[N][M];


int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> K;

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= K; j++) cin >> b[i][j] >> s[i][j];
  }

  for(int i = 1; i <= m; i++) cin >> x[i] >> y[i] >> z[i];

  auto calc = [&] (int mid) {
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) f[i][j] = 1e16;
    for(int i = 1; i <= n; i++) f[i][i] = 0;
    for(int i = 1; i <= m; i++) f[x[i]][y[i]] = min(f[x[i]][y[i]], 1LL * z[i] * mid);
    for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
      f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
      g[i][j] = cost[i][j] - f[i][j];
      if (i == j) g[i][j] = -1e16;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
//      cout << i << " " << j << " " << g[i][j] << " " << f[i][j] << " " << cost[i][j] << endl;
    }
    for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
      g[i][j] = max(g[i][j], g[i][k] + g[k][j]);
    }

    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
//      cout << i << " " << j << " " << g[i][j] << endl;
    }
    for(int i = 1; i <= n; i++) if (g[i][i] >= 0) return true;
    return false;
  };

  for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
    for(int k = 1; k <= K; k++) if (s[j][k] != -1 && b[i][k] != -1) {
      cost[i][j] = max(cost[i][j], s[j][k] - b[i][k]);
    }
  }

//  cout << calc(2);return 0;

  int l = 1, r = 1e9, ans = 0;

  while (l <= r) {
    int mid = l + r >> 1;
    if (calc(mid)) {
      ans = mid;
      l = mid + 1;
    } else r = mid - 1;
  }

  cout << ans;

}

Compilation message (stderr)

merchant.cpp: In function 'int32_t main()':
merchant.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     int mid = l + r >> 1;
      |               ~~^~~
merchant.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:30:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:31:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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