QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#612458 | #5414. Stop, Yesterday Please No More | ice_cup# | WA | 5ms | 5964kb | C++14 | 1.6kb | 2024-10-05 11:21:38 | 2024-10-05 11:21:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MID int mid=(l+r)>>1;
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
int n,m,K,k;
string s;
vector<int>d[2010];
int dp[1010][1010],tmp[1010];
void clr(){
for(int i=1000-n;i<=1000+n;i++)d[i].clear();
for(int i=1;i<=n+3;i++){
for(int j=1;j<=m+3;j++)dp[i][j]=0;
}
}
void solve(){
clr();
cin>>n>>m>>K;
cin>>s;
k=s.size();
int x=1000,y=1000;
int x1=1,x2=n,y1=1,y2=m;
d[x].push_back(y);
for(int i=0;i<k;i++){
if(s[i]=='U')x++;
if(s[i]=='D')x--;
if(s[i]=='L')y++;
if(s[i]=='R')y--;
if(x>=1000-n&&x<=1000+n)d[x].push_back(y);
x1=max(x1,x-1000+1);
x2=min(x2,1000-x+n);
y1=max(y1,y-1000+1);
y2=min(y2,1000-y+m);
// cout<<x<<' '<<y<<endl;
}
// cout<<x1<<' '<<x2<<' '<<y1<<' '<<y2<<endl;
for(int i=1000-n;i<=1000+n;i++){
sort(d[i].begin(),d[i].end());
int top=unique(d[i].begin(),d[i].end())-d[i].begin();
for(int j=0;j<=m;j++)tmp[j]=0;
for(int j=0;j<top;j++){
int y=d[i][j]-1000;
if(max(1,y1-y)>min(m,y2-y))continue;
tmp[max(1,y1-y)]++;
tmp[min(m,y2-y)+1]--;
}
for(int j=1;j<=m;j++)tmp[j]+=tmp[j-1];
int x=i-1000;
if(max(1,x1-x)>min(n,x2-x))continue;
for(int j=1;j<=m;j++){
dp[max(1,x1-x)][j]+=tmp[j];
dp[min(n,x2-x)+1][j]-=tmp[j];
}
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]+=dp[i-1][j];
if(dp[i][j]==K)cnt++;
}
}
cout<<cnt<<endl;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int TTT;
cin>>TTT;
// TTT=1;
while(TTT--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3784kb
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: 5ms
memory: 5964kb
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 1 0 0 0 0 0 240 0 0 0 0 0 18 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 61 0 0 2 0 0 0 0 0 0 0 0 0 22 0 51 0 0 0 0 0 26 16 8 0 0 0 0 0 0 0 0 0 44 0 0 0 0 4 30 0 0 12 0 0 3 0 66 0 0 4 0 0 0 0 0 0 19 0 0 0 0 48 0 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 48 0 0 225 0 0 0 0 0 0 90 0 0 228 0 30 0 16 8...
result:
wrong answer 2nd numbers differ - expected: '11', found: '1'