We maintain an array $A$ such that $A[i][j]$, for $1 \le i, j \le n+1$, is equal to the number of cows that will pass through cell $(i, j)$. We can compute the starting values of $A$ as follows: initially set $A[i][j] = 1$ for all $1 \le i, j \le N$ and $A[i][j] = 0$ otherwise. Then, process all the cells $(i, j)$ for $1 \le i, j \le N$ in row-major order; add the value of $A[i][j]$ to the cell to which the signpost in $(i, j)$ points. This algorithm takes $O(N^2)$ time to compute the initial value of $A$.

Next, we describe how to update $A$. Note that when the signpost in $(i, j)$ changes direction, the values of $A[i'][j']$ along the original path of the cow in $(i, j)$ go down by $A[i][j]$, and the values of $A[i'][j']$ along the new path of the cow go up by $A[i][j]$. To update $A$, we only need to update the values along these paths, which have length $O(N)$ and can also be computed in $O(N)$ time (by just following directions starting at $(i, j)$). Thus, updating $A$ after each day takes only $O(N)$ time.

In order to compute the total cost from $A$, we just need to sum $A[i][j]c_{i,j}$ for all cells $(i, j)$ with a vat. This takes $O(N)$ time if we have $A$. Therefore, the total time complexity of this algorithm is $O(N^2 + NQ)$.

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class FollowingDirections {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        char[][] dirs = new char[n][];
        int[][] weights = new int[n + 1][n + 1];
        for (int y = 0; y < n; y++) {
            StringTokenizer tokenizer = new StringTokenizer(in.readLine());
            dirs[y] = tokenizer.nextToken().toCharArray();
            weights[y][n] = Integer.parseInt(tokenizer.nextToken());
        }
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int x = 0; x < n; x++) {
            weights[n][x] = Integer.parseInt(tokenizer.nextToken());
        }
 
        int[][] amtReach = new int[n + 1][n + 1];
        int answer = 0;
        for (int y = 0; y <= n; y++) {
            for (int x = 0; x <= n; x++) {
                if (y == n || x == n) {
                    answer += amtReach[y][x] * weights[y][x];
                } else {
                    amtReach[y][x]++;
                    if (dirs[y][x] == 'R') {
                        amtReach[y][x + 1] += amtReach[y][x];
                    } else {
                        amtReach[y + 1][x] += amtReach[y][x];
                    }
                }
            }
        }
 
        StringBuilder out = new StringBuilder();
        out.append(answer).append('\n');
        for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
            tokenizer = new StringTokenizer(in.readLine());
            int y = Integer.parseInt(tokenizer.nextToken()) - 1;
            int x = Integer.parseInt(tokenizer.nextToken()) - 1;
 
            int v = y;
            int u = x;
            while (v != n && u != n) {
                if (dirs[v][u] == 'R') {
                    u++;
                } else {
                    v++;
                }
                amtReach[v][u] -= amtReach[y][x];
            }
            answer -= amtReach[y][x] * weights[v][u];
 
            if (dirs[y][x] == 'R') {
                dirs[y][x] = 'D';
            } else {
                dirs[y][x] = 'R';
            }
 
            v = y;
            u = x;
            while (v != n && u != n) {
                if (dirs[v][u] == 'R') {
                    u++;
                } else {
                    v++;
                }
                amtReach[v][u] += amtReach[y][x];
            }
            answer += amtReach[y][x] * weights[v][u];
 
            out.append(answer).append('\n');
        }
        System.out.print(out);
    }
}

David Hu's code:

N = int(input())
grid = [[0 for i in range(N)] for j in range(N)]
A = [0] * N
 
for i in range(N):
    row, A[i] = input().split()
    for j in range(N):
        grid[i][j] = row[j]
    A[i] = int(A[i])
 
B = list(map(int, input().split()))
 
dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
 
def compute():
    res = 0
    for i in range(N):
        res += dp[i][N] * A[i]
        res += dp[N][i] * B[i]
    return res
 
def update(x, y, val):
    while True:
        dp[x][y] += val
        if (x == N or y == N):
            return
        if (grid[x][y] == 'R'):
            y += 1
        else:
            x += 1
 
for i in range(N + 1):
    for j in range(N + 1):
        if (i != N and j != N):
            dp[i][j] = 1
        if (i != 0 and j != N and grid[i - 1][j] == 'D'):
            dp[i][j] += dp[i - 1][j]
        if (i != N and j != 0 and grid[i][j - 1] == 'R'):
            dp[i][j] += dp[i][j - 1]
 
print(compute())
 
Q = int(input())
 
for q in range(Q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    cur = dp[x][y]
    update(x, y, -cur)
    if (grid[x][y] == 'R'):
        grid[x][y] = 'D'
    else:
        grid[x][y] = 'R'
    update(x, y, cur)
    print(compute())