QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89367 | #5414. Stop, Yesterday Please No More | ylf20010818# | WA | 1ms | 3596kb | C++17 | 2.9kb | 2023-03-19 21:30:45 | 2023-03-19 21:30:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;
void solve(){
int n,m,k;
cin>>n>>m>>k;
int dd=n*m;
string s;
cin>>s;
int up=0,ri=0;
int upm=-inf,upd=inf;
int rim=-inf,rid=inf;
for(int i=0;i<s.length();i++){
char ch=s[i];
if(s[i]=='U') up++;
else if(s[i]=='D') up--;
else if(s[i]=='R') ri--;
else ri++;
upm=max(upm,up);
upd=min(upd,up);
rim=max(rim,ri);
rid=min(rid,ri);
}
n=n-abs(upm)-abs(upd);
m=m-abs(rim)-abs(rid);
if(n*m<=0&&k==0){
cout<<dd<<"\n";
return;
} else if(n*m<=0&&k>0){
cout<<0<<"\n";
return;
}
int num=n*m-k;
vector<vector<int>> a(abs(upm)+abs(upd)+50,vector<int>(abs(rim)+abs(rid)+50,0));
int ix=abs(rid)+1;
int iy=abs(upd)+1;
int inx=ix,iny=iy;
int ns=abs(upm)+abs(upd)+1;
int ms=abs(rim)+abs(rid)+1;
a[ix][iy]=1;
for(int i=0;i<s.length();i++){
if(s[i]=='U') iy++;
else if(s[i]=='D') iy--;
else if(s[i]=='R') ix--;
else ix++;
a[iy][ix]=1;
}
// for(int i=1;i<=ns;i++){
// for(int j=1;j<=ms;j++){
// cout<<a[i][j];
// }
// cout<<"\n";
// }
for(int i=1;i<=ns;i++){
for(int j=1;j<=ms;j++){
a[i][j]+=a[i-1][j];
}
}
for(int i=1;i<=ns;i++){
for(int j=1;j<=ms;j++){
a[i][j]+=a[i][j-1];
}
}
// for(int i=1;i<=ns;i++){
// for(int j=1;j<=ms;j++){
// cout<<a[i][j];
// }
// cout<<"\n";
// }
n=n+abs(upm)+abs(upd);
m=m+abs(rim)+abs(rid);
// cout<<ns<<" "<<ms<<"\n";
// cout<<iny<<" "<<inx<<"\n";
int ans=0;
// cout<<py<<" "<<px<<"\n";
// cout<<1+upm<<" "<<1+rim<<"\n";
// cout<<n+upd<<" "<<m+rid<<"\n";
// cout<<num<<'\n';
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// if(ns+i-iny<1+upm||ms-inx+j<1+rim||i+1-iny>n+upd||j+1-inx>m+rid) continue;
// cout<<i-iny+1<<" "<<j-inx+1<<" "<<ns+i-iny<<" "<<ms-inx+j<<"\n";
// cout<<1+upm<<" "<<1+rim<<" "<<n+upd<<" "<<m+rid<<"\n";
int n2=min(ns+i-iny,n+upd),m2=min(ms-inx+j,m+rid);
int n1=max(1+i-iny,1+upm),m1=max(1+j-inx,1+rim);
// cout<<i<<" "<<j<<"\n";
// cout<<n2<<" "<<m2<<" "<<n1<<" "<<m1<<"\n";
// int dy=n2-n1+1,dx=m2-m1+1;
int py=i-iny+1,px=j-inx+1;
int now=a[n2-py+1][m2-px+1]-a[n1-py][m2-px+1]-a[n2-py+1][m1-px]+a[n1-py][m1-px];
// cout<<i<<" "<<j<<" "<<now<<"\n";
if(now==num) ans++;
}
}
cout<<ans<<"\n";
a.clear();
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3484kb
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: 1ms
memory: 3596kb
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:
21 11 4 99 15 15 0 240 0 0 0 0 8 18 0 0 1 19 0 0 2 0 10 0 0 30 16 0 0 13 10 9 15 7 320 11 2 5 0 0 7 0 4 0 0 9 0 22 0 51 0 8 6 4 2 48 28 8 7 0 0 17 0 4 0 10 0 44 0 15 2 0 4 30 1 0 105 10 26 17 0 66 0 11 28 0 0 56 0 0 56 90 14 0 121 0 48 8 36 13 0 30 7 0 3 11 0 0 0 34 0 38 0 34 0 5 0 0 27 48 9 3 225 0...
result:
wrong answer 1st numbers differ - expected: '228', found: '21'