Submission #109720

#	Time	Username	Problem	Language	Result	Execution time	Memory
109720		Arturgo	Travelling Merchant (APIO17_merchant)	C++14	0 / 100	1072 ms	3064 KiB

merchant

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

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

int nbMarches, nbChemins, nbObjets;

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

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

bool estPossible(double 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];
    }
  }

  vector<double> dyn(nbMarches, 0);

  bool change = true;
  for(int iFois = 0;change;iFois++) {
    change = false;

    if(iFois > nbMarches)
      return true;

    for(int iDeb = 0;iDeb < nbMarches;iDeb++) {
      for(int iFin = 0;iFin < nbMarches;iFin++) {
	if(dyn[iDeb] + valeurs[iDeb][iFin] < dyn[iFin]) {
	  change = true;
	  dyn[iFin] = dyn[iDeb] + valeurs[iDeb][iFin];
	}
      }
    }
  }

  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;
    }
  }

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

  cout << (int)(deb + 0.000001) << endl;
  return 0;
}

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