比赛 4043级2023省选模拟赛6 评测结果 AAAAAAAAAAAAAAA
题目名称 Following Directions 最终得分 100
用户昵称 yrtiop 运行时间 1.297 s
代码语言 C++ 内存使用 18.24 MiB
提交时间 2023-03-28 09:01:46
显示代码纯文本
#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 1505;

int read() {
    int s = 0;
    char c = getchar();
    for(;c < '0'||c > '9';c = getchar());
    for(;c >= '0'&&c <= '9';c = getchar())
        s = (s << 1) + (s << 3) + (c ^ '0');
    return s;
}

int f[maxn][maxn],row[maxn],col[maxn],n,m,sum[maxn][maxn],ans[maxn];
char s[maxn][maxn];
bool tag[maxn][maxn];

struct node {
    int x,y,s;
    node() {
        x = y = s = 0;
    }
    node(int x,int y,int s):x(x),y(y),s(s){}
} E[maxn];

int dfs(int i,int j) {
    if(f[i][j])
        return f[i][j];
    if(i == n + 1)
        return col[j];
    if(j == n + 1)
        return row[i];
    if(s[i][j] == 'R')
        return f[i][j] = dfs(i , j + 1);
    else
        return f[i][j] = dfs(i + 1 , j);
}

int calc(int i,int j,int v,int z) {
    if(i == n + 1)
        return col[j];
    if(j == n + 1)
        return row[i];
    int x,y;
    if(s[i][j] == 'R')
		x = i,y = j + 1;
    else
		x = i + 1,y = j;
	sum[x][y] += v * z;
	return calc(x , y , v , z);
}

int main() {
	freopen("zunxun.in","r",stdin);
	freopen("zunxun.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;++ i)
        scanf("%s %d",s[i] + 1,&row[i]);
    for(int i = 1;i <= n;++ i)
        scanf("%d",&col[i]);
    for(int i = 1;i <= n;++ i)
        for(int j = 1;j <= n;++ j)
            ans[0] += f[i][j] = dfs(i , j);
    printf("%d\n",ans[0]);
    scanf("%d",&m);
    for(int i = 1;i <= m;++ i) {
        int x,y;
        scanf("%d %d",&x,&y);
        E[i] = node(x , y , 1);
        tag[x][y] = true;
    }
    for(int i = 1;i <= n;++ i) {
        for(int j = 1;j <= n;++ j) {
            sum[i][j] += 1;
            if(s[i][j] == 'R')
                sum[i][j + 1] += sum[i][j];
            else
                sum[i + 1][j] += sum[i][j];
        }
    }
    for(int i = 1;i <= m;++ i) {
        int x = E[i].x,y = E[i].y;
        ans[i] = ans[i - 1] - sum[x][y] * calc(x , y , -1 , sum[x][y]);
        if(s[x][y] == 'R')
            s[x][y] = 'D';
        else
            s[x][y] = 'R';
        ans[i] += sum[x][y] * calc(x , y , 1 , sum[x][y]);
        printf("%d\n",ans[i]);
    }
    return 0;
}