Limites de temps et de mémoire (C++)

• Temps : 2,5 s sur une machine à 1 GHz.
• Mémoire : 1 000 ko.

Contraintes

Entrée

Sortie

Exemples

Exemple 1

entrée :

5 5
3
2 3
3 4
4 4

sortie :

4

Exemple 2

entrée :

6 20
4
5 6
1 1
6 1
3 7

sortie :

9

Exemple 3

entrée :

10 10
5
9 1
7 6
5 8
4 1
3 2

sortie :

11

 voilà ce que j'ai fait, je passe 4 tests sur 11, et je passe tous les tests donnés en exemple

//code 5
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
const int INF = INT_MAX;
int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int C, R, N;
  std::cin >> C >> R >> N;
  std::vector<std::pair<int, int>> shelves(N);
  for (int i = 0; i < N; ++i)
  {
    std::cin >> shelves[i].first >> shelves[i].second;
  }
  // Trier les étagères par lignes en ordre décroissant, puis par colonnes en ordre croissant
  sort(shelves.begin(), shelves.end(), [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
  });
  int min_total_distance = INF;
  // Commencer par chaque colonne de la première ligne
  for (int start_col = 1; start_col <= C; ++start_col)
  {
    int total_distance = 0;
    int current_col = start_col;
    int current_row = 0;
    for (int i = 0; i < N; )
    {
      int max_height = 0;
      // Collecte des livres dans la colonne actuelle et les colonnes adjacentes tout en grimpant
      while (i < N && (shelves[i].first == current_col || shelves[i].first == current_col - 1 || shelves[i].first == current_col + 1))
      {
        max_height = std::max(max_height, shelves[i].second);
        i++;
      }
      // Calcule la distance verticale jusqu'à la hauteur maximale dans cette étagère
      total_distance += (max_height - current_row);
      current_row = max_height;
      // Passe à la colonne suivante s'il y a plus d'étagères
      if (i < N)
      {
        // Passe horizontalement à la colonne du livre suivant
        //total_distance += std::abs(shelves[i].first - current_col);
        current_col = shelves[i].first;
        // Réinitialise la rangée actuelle à 0 puisque nous devons remonter depuis le sol
        current_row = 0;
      }
    }
    // Mettre à jour la distance totale minimale trouvée
    min_total_distance = std::min(min_total_distance, total_distance);
  }
  std::cout << min_total_distance << "\n";
  return 0;
}