fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int main() {
  8.     // Tối ưu I/O
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.  
  12.     long long H, W, N;
  13.     if (!(cin >> H >> W >> N)) return 0;
  14.  
  15.     vector<pair<long long, long long>> doors(N);
  16.     for (int i = 0; i < N; ++i) {
  17.         cin >> doors[i].first >> doors[i].second;
  18.     }
  19.  
  20.     // Sắp xếp các cửa theo hàng (row), sau đó theo cột (col)
  21.     sort(doors.begin(), doors.end());
  22.  
  23.     long long opt1_cost = 0;
  24.     long long sum_creturn = 0;
  25.     vector<long long> deltas;
  26.  
  27.     vector<long long> X;
  28.     for (int i = 0; i < N; ++i) {
  29.         X.push_back(doors[i].second);
  30.  
  31.         // Kích hoạt xử lý khi đã gom đủ các cột của một hàng
  32.         if (i == N - 1 || doors[i].first != doors[i+1].first) {
  33.             sort(X.begin(), X.end());
  34.             X.erase(unique(X.begin(), X.end()), X.end());
  35.  
  36.             // Chiến lược 1: Chỉ tiếp cận từ cột 1 (không bao giờ sang cột W)
  37.             opt1_cost += 2LL * (X.back() - 1);
  38.  
  39.             // Chiến lược 2: Chia cắt khoảng cách lớn nhất, tiếp cận từ cả cột 1 và cột W
  40.             long long max_gap = max(X.front() - 1, W - X.back());
  41.             for (size_t j = 0; j < X.size() - 1; ++j) {
  42.                 max_gap = max(max_gap, X[j+1] - X[j]);
  43.             }
  44.  
  45.             long long c_ret = 2LL * (W - 1 - max_gap);
  46.             sum_creturn += c_ret;
  47.  
  48.             // Lượng chi phí thay đổi nếu quyết định đi xuyên qua hàng này (từ 1 -> W hoặc W -> 1)
  49.             deltas.push_back((W - 1) - c_ret);
  50.  
  51.             X.clear();
  52.         }
  53.     }
  54.  
  55.     // Luôn có sẵn vô hạn hàng rỗng để đi xuyên qua với chi phí W - 1 (cần tối đa 2 hàng để cân bằng tính chẵn lẻ)
  56.     deltas.push_back(W - 1);
  57.     deltas.push_back(W - 1);
  58.  
  59.     sort(deltas.begin(), deltas.end());
  60.  
  61.     long long S_neg = 0;
  62.     int K = 0;
  63.     for (long long d : deltas) {
  64.         if (d < 0) {
  65.             S_neg += d;
  66.             K++;
  67.         }
  68.     }
  69.  
  70.     long long opt2_cost = 0;
  71.     // Bắt buộc số lần đi xuyên qua các hàng (từ cột này sang cột kia) phải là số chẵn và >= 2 để có thể sử dụng cột W
  72.     if (K % 2 == 1) {
  73.         if (K > 1) {
  74.             opt2_cost = sum_creturn + S_neg + min(-deltas[K-1], deltas[K]);
  75.         } else {
  76.             opt2_cost = sum_creturn + S_neg + deltas[1];
  77.         }
  78.     } else {
  79.         if (K >= 2) {
  80.             opt2_cost = sum_creturn + S_neg;
  81.         } else {
  82.             opt2_cost = sum_creturn + deltas[0] + deltas[1];
  83.         }
  84.     }
  85.  
  86.     // Kết quả cuối cùng là giá trị tối ưu giữa việc không bao giờ dùng thang máy cột W và có dùng thang máy cột W
  87.     cout << min(opt1_cost, opt2_cost) << "\n";
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6
stdout
copy 
18
https://ideone.com/HkBpxt
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!