제출 #109721

#제출 시각아이디문제언어결과실행 시간메모리
109721Arturgo여행하는 상인 (APIO17_merchant)C++14
0 / 100
82 ms1408 KiB
#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]; 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; while(fin - deb > 1) { int mil = (deb + fin) / 2; if(estPossible(mil)) { deb = mil; } else { fin = mil; } } cout << deb << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...