Đường đi lớn nhất - MarisaOJ: Marisa Online Judge

Đường đi lớn nhất

Time limit: 1000 ms
Memory limit: 256 MB
Cho một bảng $A$ kích cỡ $n\times n$ chứa các số nguyên từ $1$ đến $1000$. Gọi $f(i,j)$ là tổng lớn nhất trên đường đi từ ô $(1,1)$ đến ô $(i,j)$ nếu chỉ được đi sang ngang hoặc đi xuống dưới một ô. Có $n$ truy vấn, mỗi truy vấn dạng $(v,x,y)$, tăng giá trị $A_{x,y}$ lên $v$ trong đó $v$ là $1$ hoặc $-1$. Hãy tính tổng của $f$ với mọi $(i,j)$ sau mỗi truy vấn. ### Input - Dòng đầu tiên gồm số nguyên $n \le 1500$. - $n$ dòng tiếp theo, mỗi dòng gồm $n$ số nguyên $A_{i,j}$ ### Output - Dòng đầu tiên là tổng $f$ ban đầu. - $n$ dòng tiếp theo là tổng $f$ sau các truy vấn. ### Ví dụ Input: ``` 5 3 3 5 0 5 4 4 2 4 3 4 4 2 1 3 4 3 2 4 2 2 3 3 2 4 1 1 1 1 1 3 -1 5 2 -1 4 3 -1 2 4 ``` Output: ``` 420 445 453 451 448 442 ```