记录编号	607113	评测结果	AAAAAAAAAATTTTT
题目名称	3863.[USACO23 Jan Silver] Following Directions	最终得分	67
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	23.687 s
提交时间	2025-10-05 17:06:49	内存使用	19.65 MiB

#include <iostream>
using namespace std;

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> T read(T& x) {
  return x = read<T>();
}

template <typename T, typename ...Others> void read(T &x, Others& ...y) {
  read(x);
  read(y...);
}

void read(char *str) {
  char ch = getchar();
  for (; isspace(ch); ch = getchar());
  for (; !isspace(ch); ch = getchar()) *str++ = ch;
  *str = 0;
}

template <typename T> void write(T x, char ed = '\n') {
  int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while(x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}

const int MAXN = 1510;

int n, q;
char a[MAXN][MAXN];
int price[MAXN][MAXN];
int cnt[MAXN][MAXN];
pair<int, int> ending[MAXN][MAXN];

void initialize(int x, int y, int ex, int ey) {
  if (x != ex || y != ey) {
    cnt[ex][ey]++;
  }
  ending[x][y] = make_pair(ex, ey);
  if (a[x - 1][y] == 'D') initialize(x - 1, y, ex, ey);
  if (a[x][y - 1] == 'R') initialize(x, y - 1, ex, ey);
}

int calcsum() {
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    res += cnt[i][n + 1] * price[i][n + 1];
    res += cnt[n + 1][i] * price[n + 1][i];
  }
  return res;
}

int calccnt(int x, int y) {
  int res = 0;
  if (a[x - 1][y] == 'D') res += calccnt(x - 1, y);
  if (a[x][y - 1] == 'R') res += calccnt(x, y - 1);
  return res;
}

void CalcCntAndChangeEnding(int x, int y, int stdx, int stdy, int &cnt) {
  ending[x][y] = ending[stdx][stdy];
  cnt++;
  if (a[x][y - 1] == 'R') CalcCntAndChangeEnding(x, y - 1, stdx, stdy, cnt);
  if (a[x - 1][y] == 'D') CalcCntAndChangeEnding(x - 1, y, stdx, stdy, cnt);
}

void change(int x, int y) {
  pair<int, int> endingbefore = ending[x][y];
  if (a[x][y] == 'D') {
    a[x][y] = 'R';
    ending[x][y] = ending[x][y + 1];
  } else {
    a[x][y] = 'D';
    ending[x][y] = ending[x + 1][y];
  }

  int connectcnt = 0;
  CalcCntAndChangeEnding(x, y, x, y, connectcnt);

  cnt[endingbefore.first][endingbefore.second] -= connectcnt;
  cnt[ending[x][y].first][ending[x][y].second] += connectcnt;
}

int main() {
  freopen("zunxun.in", "r", stdin);
  freopen("zunxun.out", "w", stdout);
  read(n);
  for (int i = 1; i <= n; ++i) {
    read(a[i] + 1);
    read(price[i][n + 1]);
  }
  for (int i = 1; i <= n; ++i) {
    read(price[n + 1][i]);
  }

  for (int i = 1; i <= n; ++i) {
    initialize(i, n + 1, i, n + 1);
    initialize(n + 1, i, n + 1, i);
  }

  write(calcsum());
  read(q);
  for (int a, b; q--; ) {
    read(a, b);
    change(a, b);
    write(calcsum());
  }
  return 0;
}