{"code":"2023jansilver2","name":"USACO 2023 January Contest, Silver, Following Directions","description":"Nông dân John có một trang trại lưới ô vuông kích thước $(N + 1) \\times (N + 1)$ ($1 \\le N \\le 1500$). Ô $(i, j)$ đại diện cho ô ở hàng $i$ từ trên xuống và cột $j$ từ trái sang. Có một con bò sống ở mỗi ô $(i, j)$ với $1 \\le i, j \\le N$, mỗi ô như vậy cũng chứa một biển hiệu hướng sang phải hoặc xuống dưới. Mỗi ô $(i, j)$ thỏa mãn $i = N + 1$ hoặc $j = N + 1$, ngoại trừ $(N + 1, N + 1)$, chứa một bể thức ăn cho bò. Mỗi bể chứa thức ăn có giá khác nhau, bể ở ô $(i, j)$ có giá $c_{i, j}$ ($1 \\le c_{i, j} \\le 500$) để cho một con bò ăn. \r\n\r\nMỗi ngày vào giờ ăn tối, nông dân John rung chuông ăn tối, và mỗi con bò sẽ đi theo biển hiệu cho đến khi chúng đi đến một bể thức ăn, và ăn thức ăn ở bể đó. Sau đó, các con bò quay trở về chỗ ban đầu vào ngày tiếp theo.\r\n\r\nĐể quản lý chi phí, nông dân John muốn biết tổng chi phí để cho tất cả bò ăn mỗi ngày. Tuy nhiên, vào mỗi ngày, trước trời tối, con bò ở một ô $(i, j)$ nào đó lật ngược hướng của biển hiệu của nó (sang phải thành xuống dưới và ngược lại). Biển hiệu sẽ hướng về hướng này cho những ngày tiếp theo, trừ khi nó được lật lại một lần nữa.\r\n\r\nBạn được cho tọa độ của biển hiệu bị lật trong mỗi ngày, in ra chi phí cho mỗi ngày (tổng có $Q$ ngày, $1 \\le Q \\le 1500$).\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa số nguyên $N$ ($1 \\le N \\le 1500$).\r\n- $N + 1$ dòng tiếp theo chứa các hàng của lưới từ trên xuống dưới, chứa hướng ban đầu của các biển hiệu và chi phí $c_{i, j}$ của mỗi bể. $N$ dòng đầu tiên chứa một xâu $N$ chứa hướng `R` hoặc `D` (biểu diễn chỉ hướng sang phải hoặc xuống dưới), theo sau đó là chi phí $c_{i, N + 1}$. Dòng thứ $N + 1$ chứa $N$ chi phí $c_{N + 1, j}$.\r\n- Dòng tiếp theo chứa $Q$ ($1 \\le Q \\le 1500$).\r\n- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $i$ và $j$ ($1 \\le i, j \\le N$), tọa độ của ô mà biển hiệu bị lật trong ngày tương ứng.\r\n\r\n#### Output\r\n- $Q + 1$ dòng, chi phí ban đầu và theo sau là chi phi sau mỗi lần lật biển.\r\n\r\n#### Scoring\r\n- Subtask 1: $1 \\le N, Q, \\le 50$\r\n- Subtask 2: $1 \\le N, Q \\le 250$\r\n- Subtask 3: Các hướng ban đầu của các biển hiệu được sinh ngẫu nhiên.\r\n- Subtask 4: Không có ràng buộc gì thêm\r\n\r\n#### Example\r\n\r\n!!!question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        2\r\n        RR 1\r\n        DD 10\r\n        100 500\r\n        4\r\n        1 1\r\n        1 1\r\n        1 1\r\n        2 1\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```\r\n        602\r\n        701\r\n        602\r\n        701\r\n        1501\r\n        ```\r\n\r\n    ??? warning \"Note\"\r\n        Trước lần lật đầu tiên, con bò ở $(1,1)$ và $(1,2)$ có chi phí nuôi là $11$, con bò ở $(2,1)$ có chi phí nuôi là $100100$, và con bò ở $(2,2)$ có chi phí nuôi là $500500$, với tổng chi phí là $602602$. Sau lần lật đầu tiên, hướng của biển báo tại $(1,1)$ thay đổi từ R thành D, và con bò ở $(1,1)$ bây giờ có chi phí nuôi là $100100$ (trong khi các con bò khác vẫn giữ nguyên), do đó tổng chi phí bây giờ là $701701$. Lần lật thứ hai và thứ ba chuyển biển báo trở lại như cũ. Sau lần lật thứ tư, các con bò ở $(1,1)$ và $(2,1)$ bây giờ có chi phí nuôi là $500500$, với tổng chi phí là $15011501$.","points":1000.0,"partial":true,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}