Submission #278678

#	Time	Username	Problem	Language	Result	Execution time	Memory
278678		toonewbie	Travelling Merchant (APIO17_merchant)	C++17	33 / 100	1094 ms	2808 KiB

merchant

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;

int n, m, K;
ll d[200][200], a[200][200];
int b[200][2000], s[200][2000];

bool C(ll t) {
  rep(i, n) rep(j, n) a[i][j] = -INF;
  rep(i, n) rep(j, n) {
    if (i == j || d[i][j] == INF)
      continue;
    a[i][j] = -t * d[i][j];
    rep(k, K) {
      if (b[i][k] == -1 || s[j][k] == -1)
        continue;
      a[i][j] = max(a[i][j], s[j][k] - b[i][k] - t * d[i][j]);
    }
  }
  rep(k, n) rep(i, n) rep(j, n) { a[i][j] = max(a[i][j], a[i][k] + a[k][j]); }
  rep(i, n) {
    if (a[i][i] >= 0)
      return true;
  }
  return false;
}
int main() {
  cin >> n >> m >> K;
  rep(i, n) rep(j, K) scanf("%d%d", &b[i][j], &s[i][j]);
  memset(d, 0x3f, sizeof(d));
  rep(i, n) d[i][i] = 0;
  rep(i, m) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    d[a][b] = c;
  }
  rep(k, n) rep(i, n) rep(j, n) { d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
  ll l = 0, r = INT_MAX;
  while (r - l > 1) {
    ll t = (l + r) / 2;
    if (C(t))
      l = t;
    else
      r = t;
  }
  cout << l << endl;
  return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:32:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   rep(i, n) rep(j, K) scanf("%d%d", &b[i][j], &s[i][j]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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