Submission #653044

#	Time	Username	Problem	Language	Result	Execution time	Memory
653044		pauloamed	Travelling Merchant (APIO17_merchant)	C++17	0 / 100	130 ms	1996 KiB

merchant

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 101;
const int MAXK = 1001;

int sell[MAXN][MAXK];
int buy[MAXN][MAXK];

int p1[MAXN][MAXN];
int best[MAXN][MAXN];

int p2[MAXN][MAXN];

const int INF = LLONG_MAX;

const __int128_t A = LLONG_MAX;
const __int128_t B = LLONG_MIN;

int sum(__int128_t a, __int128_t b){
  __int128_t x = a + b;
  return max(min(x, A), B);
}

bool test(int r, int n){
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(p1[i][j] == INF){
        p2[i][j] = 0;
      }else{
        p2[i][j] = best[i][j] - r * p1[i][j];
        // cout << i << " " << j << " : ";
        // cout << best[i][j] << " " << p1[i][j] << " : ";
        // cout << p2[i][j] << "\n"; 
      }
    }
  }

  for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        p2[i][j] = max(p2[i][j], sum(p2[i][k], p2[k][j]));
      }
    }
  }

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

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);
  int n, m, k; cin >> n >> m >> k;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < k; ++j){
      int ki = j / 2;
      cin >> buy[i][ki];
      cin >> sell[i][ki];
    }
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      p1[i][j] = INF;
    }
  }

  for(int i = 0; i < m; ++i){
    int a, b, c; cin >> a >> b >> c;
    a--; b--;
    p1[a][b] = c;
  }


  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      for(int l = 0; l < k; ++l){
        if(buy[i][l] > -1 && sell[j][l] > -1){
          int prof = sell[j][l] - buy[i][l];
          best[i][j] = max(prof, best[i][j]);
        }
      }
    }
  }

  {
    for(int l = 0; l < n; l++){
      for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
          p1[i][j] = min(p1[i][j], sum(p1[i][l], p1[l][j]));
        }
      }
    }
  }

  int ans = 0;
  int pot = (1LL << 60);
  while(pot){
    int mans = ans + pot;
    if(test(mans, n)) ans = mans;
    pot /= 2;
  }
  cout << ans << "\n";
}

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