Submission #57329

#	Time	Username	Problem	Language	Result	Execution time	Memory
57329		joaogui1	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	98 ms	2684 KiB

merchant

#include <bits/stdc++.h>
#define ff first
#define ss second
#define INF (1LL << 33)

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;

int n;
pii itens[128][1024];
ll g[128][128], dist[128][128], profit[128][128];

void fw(){
  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}


bool fw(ll r){

  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      dist[i][j] = r*g[i][j] - profit[i][j];

  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j){
        //dist[i][j] |= (dist[i][k] && dist[k][j]);
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }

  for(int i = 1; i <= n; ++i)
    if(dist[i][i] <= 0)  return 1;
  return 0;
}

void pre_calc(int k){
  for(int l = 1; l <= n; ++l)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= k; ++j)
        profit[l][i] = max(profit[l][i], itens[i][j].ss - itens[l][j].ff);
}

ll bin_search(ll ini, ll fim){
  ll m, ans = 0;
  while(fim - ini > 1){
    m = (fim + ini)/2;
    if(fw(m)){
      ans = m;
      ini = m;
    }
    else  fim = m;
  }
  return ans;
}


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  ll ans = 0, test = 0;
  int m, k, a, b, c;
  cin >> n >> m >> k;
  memset(dist, 0, sizeof dist);
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      g[i][j] = INF;

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= k; ++j){
      cin >> itens[i][j].ff >> itens[i][j].ss;
      if(itens[i][j].ff == -1)  itens[i][j].ff = INF;
      if(itens[i][j].ss == -1)  itens[i][j].ss = -INF;
    }
  }
  pre_calc(k);

  for(int i = 0; i < m; ++i){
    cin >> a >> b >> c;
    g[a][b] = c;
  }
  fw();
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      test = max(test, profit[i][j]);
  //cout << test << "\n";
  ans = bin_search(0, test);
  cout << ans << "\n";

  return 0;
}

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