Submission #109727

#	Time	Username	Problem	Language	Result	Execution time	Memory
109727		Arturgo	Travelling Merchant (APIO17_merchant)	C++14	100 / 100	82 ms	3320 KiB

merchant

#include <iostream>
#include <vector>
using namespace std;

const long long INFINI = 1000ll * 1000 * 1000ll;

int nbMarches, nbChemins, nbObjets;

int achats[100][1000];
int ventes[100][1000];

long long temps[100][100];
int benefices[100][100];
long long valeurs[100][100];

bool estPossible(long long profit) {
  for(int iDeb = 0;iDeb < nbMarches;iDeb++) {
    for(int iFin = 0;iFin < nbMarches;iFin++) {
      valeurs[iDeb][iFin] = profit * temps[iDeb][iFin] - benefices[iDeb][iFin];
    }
    valeurs[iDeb][iDeb] = INFINI;
  }

  for(int iPivot = 0;iPivot < nbMarches;iPivot++) {
    for(int iDeb = 0;iDeb < nbMarches;iDeb++) {
      for(int iFin = 0;iFin < nbMarches;iFin++) {
	valeurs[iDeb][iFin] = min(valeurs[iDeb][iFin], valeurs[iDeb][iPivot] + valeurs[iPivot][iFin]);
      }
    }
  }

  for(int iMarche = 0;iMarche < nbMarches;iMarche++) {
    if(valeurs[iMarche][iMarche] <= 0)
      return true;
  }

  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> nbMarches >> nbChemins >> nbObjets;

  for(int iMarche = 0;iMarche < nbMarches;iMarche++) {
    for(int iObjet = 0;iObjet < nbObjets;iObjet++) {
      cin >> achats[iMarche][iObjet] >> ventes[iMarche][iObjet];
    }
  }

  for(int iDeb = 0;iDeb < nbMarches;iDeb++)
    for(int iFin = 0;iFin < nbMarches;iFin++)
      temps[iDeb][iFin] = INFINI;
  
  for(int iChemin = 0;iChemin < nbChemins;iChemin++) {
    int deb, fin, t;
    cin >> deb >> fin >> t;
    temps[deb - 1][fin - 1] = t;
  }

  for(int iPivot = 0;iPivot < nbMarches;iPivot++) {
    for(int iDeb = 0;iDeb < nbMarches;iDeb++) {
      for(int iFin = 0;iFin < nbMarches;iFin++) {
	temps[iDeb][iFin] = min(temps[iDeb][iFin], temps[iDeb][iPivot] + temps[iPivot][iFin]);
      }
    }
  }

  for(int iDeb = 0;iDeb < nbMarches;iDeb++) {
    for(int iFin = 0;iFin < nbMarches;iFin++) {
      int benefice = 0;
      for(int iObjet = 0;iObjet < nbObjets;iObjet++) {
	if(ventes[iFin][iObjet] != -1 && achats[iDeb][iObjet] != -1)
	  benefice = max(benefice, ventes[iFin][iObjet] - achats[iDeb][iObjet]);
      }
      benefices[iDeb][iFin] = benefice;
    }
  }

  int deb = 0, fin = 1000000000 + 1;
  while(fin - deb > 1) {
    int mil = (deb + fin) / 2;
    if(estPossible(mil)) {
      deb = mil;
    }
    else {
      fin = mil;
    }
  }

  cout << deb << endl;
  return 0;
}

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