比赛 |
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;
}