Submission #558349

#	Time	Username	Problem	Language	Result	Execution time	Memory
558349		loctildore	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	100 ms	4260 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
ll n,m,c;
ll v,w,t;
ll arr[105][105];
ll pro[105][105];
ll buy[105][1069];
ll sell[105][1069];
ll grph[105][105];
bool works(ll x) {
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n; j++) {
      grph[i][j]=pro[i][j]-x*arr[i][j];
    }
    grph[i][i]=LLONG_MIN/2;
  }
  for (ll k = 0; k < n; k++) {
    for (ll i = 0; i < n; i++) {
      for (ll j = 0; j < n; j++) {
        grph[i][j]=max(grph[i][j],grph[i][k]+grph[k][j]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    if (grph[i][i]>=0) {
      return true;
    }
  }
  return false;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  for (ll i = 0; i < 105; i++) {
    for (ll j = 0; j < 105; j++) {
      arr[i][j]=INT_MAX/2;
    }
    arr[i][i]=0;
  }
  cin>>n>>m>>c;
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < c; j++) {
      cin>>buy[i][j]>>sell[i][j];
    }
  }
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n; j++) {
      for (ll k = 0; k < c; k++) {
        if (buy[i][k]!=-1&&sell[j][k]!=-1) {
          pro[i][j]=max(pro[i][j],sell[j][k]-buy[i][k]);
        }
      }
    }
  }
  for (ll i = 0; i < m; i++) {
    cin>>v>>w>>t;
    v--;w--;
    arr[v][w]=t;
  }
  for (ll k = 0; k < n; k++) {
    for (ll i = 0; i < n; i++) {
      for (ll j = 0; j < n; j++) {
        arr[i][j]=min(arr[i][j],arr[i][k]+arr[k][j]);
      }
    }
  }
  ll s=0, e=1000000069;
  while (s+1!=e) {
    (works((s+e)/2)?s:e)=(s+e)/2;
  }
  cout<<s<<endl;
  return 0;
}

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