QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#618937 | #5414. Stop, Yesterday Please No More | sazhi | WA | 7ms | 3776kb | C++20 | 2.2kb | 2024-10-07 11:58:15 | 2024-10-07 11:58:16 |
Judging History
answer
// author: jieda
// file: cpp
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
# define fi first
# define se second
# define all(x) x.begin(),x.end()
# define stst stringstream
# define pb push_back
# define pf push_front
# define pp push
# define lowbit(x) (x)&(-x)
# define fa(i,op,n) for (int i = op; i <= n; i++)
# define fb(j,op,n) for (ll j = op; j >= n; j--)
# define fg(i,op,n) for (ll i = op; i != n; i = ne[i])
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const ll N = 2e5+10,INF = 0x3f3f3f3f,mod = 1e9+7;
const ll MOD = 212370440130137957ll;//hash(hight)
const int base = 131;
const double eps = 1e-3;
const int seed=10086,mo=1e6+7; //hash(lower)
int prime = 233317;
void solve(){
int n,m,k;cin>>n>>m>>k;
string s;cin>>s;s = " "+s;int M = s.size()-1;
int U = 1,D = n,L = 1,R = m;
for(int i = 1,u = 1,d = n,l = 1,r = m;i<=M;i++){
if(s[i] == 'U') u++,d++;
if(s[i] == 'D') u--,d--;
if(s[i] == 'L') l++,r++;
if(s[i] == 'R') l--,r--;
U = max(u,U);
D = min(d,D);
L = max(l,L);
R = min(r,R);
}
if(k == 0){
cout<<n*m<<'\n';
return ;
}
if(U>D||L>R){
cout<<0<<'\n';
return ;
}
int delt = (D-U+1)*(R-L+1)-k;
vector<vector<int>> f(2*n+5,vector<int>(2*m+5));
f[n+1][m+1] = 1;
for(int i = 1,x = n+1,y = m+1;i<=M;i++){
if(s[i] == 'U') x++;
else if(s[i] == 'D') x--;
else if(s[i] == 'L') y++;
else if(s[i] == 'R') y--;
f[x][y] = 1;
}
for(int i = 1;i<=2*n+1;i++){
for(int j = 1;j<=2*m+1;j++){
f[i][j] += f[i][j-1];
}
}
for(int i = 1;i<=2*n+1;i++){
for(int j = 1;j<=2*m+1;j++){
f[i][j] += f[i-1][j];
}
}
ll ans = 0;
int x = n+1,y = m+1;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
int nowx= x-i,nowy = y-j;
int res = f[D+nowx][R+nowy]-f[U-1+nowx][R+nowy]-f[D+nowx][L-1+nowy]+f[U-1+nowx][L-1+nowy];
if(res == delt) ans++;
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t = 1;
cin>>t;
while(t--){
solve();
}
return 0;
}
/*
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
3 4 5 3 ULDDRR 4 5 0 UUUUUUU 4 5 10 UUUUUUU
output:
2 20 0
result:
ok 3 number(s): "2 20 0"
Test #2:
score: -100
Wrong Answer
time: 7ms
memory: 3776kb
input:
1060 19 12 0 UDLDDUUUUDDDLLRDUDUURULUUUDRDUDRDRLRLRLULULLLDLDDRLUUUURUUUDDRLLRUUUDULURUULLRDRLRDDURDUUURRRLURLRUULRRUDURDLUUURDLURDDLUUURDDRLLURRDLRUDLRDRLLRRDRDDLDRURRRLUDULLLRUUDLRRURRDLLRRRDLLRDDDLRLRURURDDDL 11 1 0 UR 3 18 33 UDRLR 17 11 132 RLDRDLDRUU 6 10 13 UULUDDLRDLUUDLDD 1 15 0 D 6 20 50 D...
output:
228 11 20 99 18 15 34 240 15 0 0 13 14 18 26 16 1 19 108 8 2 2 3 7 0 30 16 21 0 8 10 9 15 5 320 11 7 3 0 0 12 0 11 0 0 14 0 22 36 51 23 7 6 4 2 48 28 8 63 22 49 13 10 4 108 10 18 44 0 15 9 0 4 30 14 99 105 10 14 17 0 66 10 11 28 52 34 56 33 14 56 90 14 0 121 3 48 30 36 13 0 30 7 8 3 11 16 45 20 34 0...
result:
wrong answer 606th numbers differ - expected: '1', found: '24'