Submission #554011

#	Time	Username	Problem	Language	Result	Execution time	Memory
554011		d4xn	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	934 ms	1048576 KiB

merchant

#pragma GCC optimize ("Ofast")
//#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
#define UB upper_bound
#define LB lower_bound
#define pb push_back
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define vii vector<ii>
#define vvii vector<vii>
#define vll vector<ll>
#define vld vector<ld>

const int N = 101, K = 1001, M = 10001, inf = 1e9;

int n, m, k, ans;
vii adj[N];
bool vis[N][N];
int p[N];
int buy[N][K];
int sell[N][K];
int mx[K];
vi cycle;

int best() {
  int cnt = 0;

  for (int j = 0; j < k; j++) {
    mx[j] = 0;
    for (int i = 1; i < cycle.size()-1; i++) {
      mx[j] = max(mx[j], sell[cycle[i]][j]);
    }

    int b = buy[0][j];
    if (b != -1 && b < mx[j]) {
      cnt += mx[j] - b;
    }
  }

  return cnt;
}

void dfs(int u = 0, int par = 0, int d = 0) {
  vis[par][u] = 1;
  p[u] = par;

  for (auto &[v, w] : adj[u]) {
    if (vis[u][v]) continue;
    
    if (v == 0) {
      cycle.clear();
      cycle.pb(0);
      while (u != 0) {
        cycle.pb(u);
        u = p[u];
      }
      cycle.pb(0);
      reverse(all(cycle));

      ans = max(ans, best() / (d+w));
    }
    else dfs(v, u, d+w);
  }

  //vis[par][u] = 0;
}

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

  ans = 0;
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      int b, s;
      cin >> b >> s;
      buy[i][j] = b;
      sell[i][j] = s;

      /*if (buy[i][j] != -1 && sell[i][j] != -1) {
        assert(buy[i][j] >= sell[i][j]);
      }*/
    }
  }

  while (m--) {
    int x, y, z;
    cin >> x >> y >> z;
    x--; y--;
    adj[x].pb(mp(y, z));
  }

  dfs();

  cout << ans << "\n";

  return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'long long int best()':
merchant.cpp:44:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 1; i < cycle.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~

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