oj.uz

답안 #109721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
109721 2019-05-07T18:57:15 Z Arturgo 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 82 ms 1408 KB 
#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;
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 1272 KB Output is correct
2 Correct 37 ms 1400 KB Output is correct
3 Correct 37 ms 1280 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 7 ms 896 KB Output is correct
11 Correct 8 ms 896 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Incorrect 12 ms 896 KB Output isn't correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 8 ms 896 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 1280 KB Output is correct
2 Correct 82 ms 1320 KB Output is correct
3 Correct 49 ms 1280 KB Output is correct
4 Correct 74 ms 1280 KB Output is correct
5 Correct 46 ms 1280 KB Output is correct
6 Correct 42 ms 1408 KB Output is correct
7 Correct 8 ms 768 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 13 ms 896 KB Output is correct
10 Correct 9 ms 896 KB Output is correct
11 Incorrect 8 ms 896 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 768 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 8 ms 768 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Incorrect 8 ms 896 KB Output isn't correct
8 Halted 0 ms 0 KB -