Submission #701134

#	Time	Username	Problem	Language	Result	Execution time	Memory
701134		Abrar_Al_Samit	Travelling Merchant (APIO17_merchant)	C++17	12 / 100	22 ms	1180 KiB

merchant

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

const int INF = 1e18;
const int nax = 101;
vector<pair<int,int>>market[nax];

int g[nax][nax];
long long dist[nax][nax];
void PlayGround() {
  int n, m, k;
  cin>>n>>m>>k;

  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=k; ++j) {
      int b, s;
      cin>>b>>s;
      market[i].emplace_back(b, s);
    }
  }

  for(int i=1; i<=n; ++i) {
    for(int j=1; j<=n; ++j) {
      if(i!=j) dist[i][j] = INF;
    }
  }
  for(int i=0; i<m; ++i) {
    int u, v, w;
    cin>>u>>v>>w;
    g[u][v] = w;
    dist[u][v] = w;
  }


  for(int b=1; b<=n; ++b) {
    for(int a=1; a<=n; ++a) {
      for(int c=1; c<=n; ++c) {
        dist[a][c] = min(dist[a][c], dist[a][b]+dist[b][c]);
      }
    }
  }

  double ans = 0;
  for(int item=0; item<k; ++item) {
    for(int sell=2; sell<=n; ++sell) {
      if(market[1][item].first!=-1 && market[sell][item].second!=-1) {
        double profit = market[sell][item].second - market[1][item].first;
        double d = dist[1][sell] + dist[sell][1];
        ans = max(ans, profit / d);
      }
    }
  }
  int val = ans;
  cout<<val<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message (stderr)

merchant.cpp:4:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    4 | const int INF = 1e18;
      |                 ^~~~

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