oj.uz

Submission #555799

# Submission time Handle Problem Language Result Execution time Memory
555799 2022-05-01T14:47:08 Z cadmiumsky Travelling Merchant (APIO17_merchant) C++14
21 / 100
 113 ms 760 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
const ll inf = 1e9L + 5, big = 1e18 + 5;
const int nmax = 105;

void fw(int n, ll dist[nmax][nmax]) {
  for(int h = 0; h < n; h++) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++)
        dist[i][j] = max(-big, min(dist[i][j], dist[i][h] + dist[h][j]));
    }
  }
}

ll dist[nmax][nmax], cost[nmax][nmax], alter[nmax][nmax];
ll buy[nmax][nmax], sell[nmax][nmax];

bool check(int n, int coef) {
  //cerr << "Alter with coef " << coef << '\n';
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++)
      alter[i][j] = min(big, -(cost[i][j] - dist[i][j] * coef));
  }
  fw(n, alter);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) { // am dat rage si m-am uitat la modelcode, wtf??
      if(alter[i][j] + alter[j][i] <= 0)
        return 1;
    }
  }
  return 0;
}

signed main() {
  int n, m, k;
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < k; j++) {
      cin >> buy[i][j] >> sell[i][j];
      if(buy[i][j] == -1)
        buy[i][j] = inf;
      if(sell[i][j] == -1)
        sell[i][j] = -inf;
    }
  }
  for(int i = 0; i< n; i++)
    for(int j = 0; j < n; j++)
      dist[i][j] = inf;
  for(int i = 0, x, y, c; i < m; i++)
    cin >> x >> y >> c, --x, --y, dist[x][y] = min(dist[x][y], c);
  fw(n, dist);
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      cost[i][j] = 0;
      for(int h = 0; h < k; h++)
        cost[i][j] = max(cost[i][j], sell[j][h] - buy[i][h]);
    }
  }
  int l = 0, r = inf, mid;
  while(r - l > 1) {
    mid = l + r >> 1;
    if(check(n, mid))
      l = mid;
    else 
      r = mid;
  }
  cout << l << '\n';
}

Compilation message

merchant.cpp: In function 'int main()':
merchant.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     mid = l + r >> 1;
      |           ~~^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 520 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 7 ms 528 KB Output is correct
9 Correct 7 ms 520 KB Output is correct
10 Correct 7 ms 524 KB Output is correct
11 Correct 8 ms 584 KB Output is correct
12 Correct 8 ms 528 KB Output is correct
13 Correct 7 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 9 ms 524 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 8 ms 468 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 8 ms 468 KB Output is correct
20 Correct 9 ms 528 KB Output is correct
21 Correct 9 ms 468 KB Output is correct
22 Correct 7 ms 524 KB Output is correct
23 Correct 6 ms 468 KB Output is correct
24 Correct 6 ms 520 KB Output is correct
25 Correct 8 ms 528 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 6 ms 468 KB Output is correct
28 Correct 7 ms 524 KB Output is correct
29 Correct 6 ms 516 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 8 ms 532 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 9 ms 528 KB Output is correct
5 Correct 9 ms 468 KB Output is correct
6 Correct 7 ms 524 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 49 ms 712 KB Output is correct
9 Incorrect 113 ms 760 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 520 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 8 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 6 ms 468 KB Output is correct
8 Correct 7 ms 528 KB Output is correct
9 Correct 7 ms 520 KB Output is correct
10 Correct 7 ms 524 KB Output is correct
11 Correct 8 ms 584 KB Output is correct
12 Correct 8 ms 528 KB Output is correct
13 Correct 7 ms 468 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Correct 9 ms 524 KB Output is correct
16 Correct 6 ms 468 KB Output is correct
17 Correct 49 ms 712 KB Output is correct
18 Incorrect 113 ms 760 KB Output isn't correct
19 Halted 0 ms 0 KB -