fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // (Giữ nguyên các defines và hàm phụ trợ)
  5.  
  6. const int maxn = 20000 + 5; 
  7. const int max_tool_id = 10000 + 5; 
  8. const int max_steps = 1000 + 5;
  9.  
  10. int n, k, a[maxn], ans = 0;
  11. int cur[max_tool_id], nxt[maxn]; 
  12.  
  13. struct ToolInfo {
  14.     int next_use; 
  15.     int id;       
  16.     bool operator<(const ToolInfo& other) const {
  17.         if (next_use != other.next_use) {
  18.             return next_use > other.next_use; 
  19.         }
  20.         return id < other.id; 
  21.     }
  22. };
  23.  
  24. set<ToolInfo> g[max_steps]; 
  25. bool is_present[max_steps][max_tool_id]; 
  26.  
  27. inline void rf()
  28. {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(nullptr); cout.tie(nullptr);
  31. }
  32.  
  33. // KHAI BÁO SỚM
  34. inline int can_lay_len(int i, int x);
  35. inline int can_dat_xuong(int i, int x);
  36.  
  37.  
  38. // Chi phí để lấy vật x từ i-1 lên i (sau khi đã đảm bảo i có chỗ)
  39. inline int can_lay_len(int i, int x)
  40. {
  41.     if (i <= 0) return 0;
  42.  
  43.     // 1. Nếu đã có trên i, không cần làm gì
  44.     if (is_present[i][x]) return 0;
  45.  
  46.     // 2. Nếu chưa có trên i, phải lấy từ i-1 lên.
  47.     int cost = can_lay_len(i-1, x); 
  48.  
  49.     // 3. Thực hiện chuyển i-1 -> i (chi phí 1)
  50.     cost += 1;
  51.  
  52.     // 4. Đảm bảo bậc i có chỗ (tính chi phí đẩy vật xuống)
  53.     cost += can_dat_xuong(i, x); 
  54.  
  55.     // 5. Cập nhật trạng thái
  56.     // Xóa vật x khỏi bậc i-1 (Nếu i-1 > 0)
  57.     if (i > 1) {
  58.         set<ToolInfo>::iterator it;
  59.         for(it = g[i-1].begin(); it != g[i-1].end(); ++it) {
  60.             if (it->id == x) break;
  61.         }
  62.         if (it != g[i-1].end()) {
  63.             g[i-1].erase(it);
  64.             is_present[i-1][x] = false;
  65.         }
  66.     }
  67.  
  68.     // Đặt vật x lên bậc i
  69.     g[i].insert({cur[x], x});
  70.     is_present[i][x] = true;
  71.  
  72.     return cost;
  73. }
  74.  
  75. // Chi phí để đảm bảo bậc i có chỗ cho vật x (bằng cách đẩy vật cần dùng xa nhất xuống)
  76. inline int can_dat_xuong(int i, int x)
  77. {
  78.     if (i <= 0) return 0;
  79.  
  80.     if (g[i].size() < 2) return 0; // Đã có chỗ
  81.  
  82.     // Bậc i đầy: Phải đẩy vật Y xa nhất xuống.
  83.     ToolInfo to_remove = *g[i].begin(); 
  84.  
  85.     // 1. Xóa vật Y khỏi bậc i
  86.     g[i].erase(g[i].begin());
  87.     is_present[i][to_remove.id] = false;
  88.  
  89.     // 2. Chuyển vật Y xuống i-1 (chi phí 1)
  90.     int cost = 1;
  91.  
  92.     // 3. Đảm bảo vật Y có chỗ trên bậc i-1 (sẽ gây chuỗi đẩy vật)
  93.     cost += can_dat_xuong(i-1, to_remove.id);
  94.  
  95.     // 4. Đặt vật Y lên bậc i-1
  96.     if (i > 1) { // Chỉ đặt nếu i-1 > 0
  97.         g[i-1].insert(to_remove);
  98.         is_present[i-1][to_remove.id] = true;
  99.     }
  100.  
  101.     return cost;
  102. }
  103.  
  104.  
  105. signed main()
  106. {
  107.     rf();
  108.  
  109.     cin >> n >> k;
  110.     for(int i = 1; i <= k; ++i) cin >> a[i];
  111.  
  112.     // 1. Pre-calculate 
  113.     for(int i = 1; i < max_tool_id; ++i) cur[i] = k+1;
  114.     for(int i = k; i >= 1; --i)
  115.     {
  116.         int x=a[i];
  117.         nxt[i]=cur[x]; cur[x]=i;
  118.     }
  119.  
  120.     // 2. Vòng lặp chính
  121.     for(int i = 1; i <= k; ++i)
  122.     {
  123.         int x = a[i];
  124.  
  125.         // A. Cập nhật next_use
  126.         cur[x] = nxt[i];
  127.  
  128.         // B. Tính chi phí lấy lên bậc N
  129.         ans += can_lay_len(n, x);
  130.  
  131.         // C. Vật X được sử dụng và rơi về sàn (BẬC 0). 
  132.         // Xóa vật X khỏi bậc N
  133.         if (is_present[n][x]) { 
  134.             set<ToolInfo>::iterator it;
  135.             for(it = g[n].begin(); it != g[n].end(); ++it) {
  136.                 if (it->id == x) break;
  137.             }
  138.             if (it != g[n].end()) {
  139.                 g[n].erase(it);
  140.                 is_present[n][x] = false;
  141.             }
  142.         }
  143.     }
  144.  
  145.     // 3. Chi phí kết thúc (mang tất cả vật từ 1..N về sàn)
  146.     // Mỗi vật trên bậc i cần i thao tác xuống.
  147.     for(int i = 1; i <= n; ++i) {
  148.         ans += g[i].size() * i; 
  149.     }
  150.  
  151.     cout << ans << "\n";
  152.     return 0;
  153. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3 12
1 2 3 2 1 4 2 1 1 2 1 3
stdout
copy 
36
https://ideone.com/hh0mRP
language:
C++14 (gcc 8.3)
created:
2 days 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!