oj.uz

Submission #57326

# Submission time Handle Problem Language Result Execution time Memory
57326 2018-07-14T14:44:37 Z joaogui1 Travelling Merchant (APIO17_merchant) C++14
12 / 100
 110 ms 2576 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define INF (1LL << 34)

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 2296 KB Output is correct
2 Correct 42 ms 2296 KB Output is correct
3 Correct 51 ms 2296 KB Output is correct
4 Correct 8 ms 2296 KB Output is correct
5 Correct 10 ms 2296 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 9 ms 2296 KB Output is correct
8 Correct 3 ms 2296 KB Output is correct
9 Correct 8 ms 2296 KB Output is correct
10 Correct 7 ms 2296 KB Output is correct
11 Correct 10 ms 2296 KB Output is correct
12 Correct 3 ms 2296 KB Output is correct
13 Correct 9 ms 2296 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 9 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 8 ms 2296 KB Output is correct
5 Correct 9 ms 2296 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 5 ms 2296 KB Output is correct
8 Correct 7 ms 2296 KB Output is correct
9 Incorrect 11 ms 2296 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2296 KB Output is correct
2 Correct 96 ms 2576 KB Output is correct
3 Correct 48 ms 2576 KB Output is correct
4 Correct 65 ms 2576 KB Output is correct
5 Incorrect 53 ms 2576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2296 KB Output is correct
2 Correct 9 ms 2296 KB Output is correct
3 Correct 6 ms 2296 KB Output is correct
4 Correct 8 ms 2296 KB Output is correct
5 Correct 9 ms 2296 KB Output is correct
6 Correct 3 ms 2296 KB Output is correct
7 Correct 5 ms 2296 KB Output is correct
8 Correct 7 ms 2296 KB Output is correct
9 Incorrect 11 ms 2296 KB Output isn't correct
10 Halted 0 ms 0 KB -