QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364601 | #5414. Stop, Yesterday Please No More | ucup-team3294# | WA | 3ms | 3920kb | C++23 | 1.7kb | 2024-03-24 15:35:23 | 2024-03-24 15:35:24 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
void solve() {
int n,m,k,count=0;
cin>>n>>m>>k;
string a;
cin>>a;
int l1=1,r1=n,l2=1,r2=m,l1min=1,r1max=n,l2min=1,r2max=m;
for(int i=0; i<a.size(); i++) {
if(a[i]=='U') {
l1--,r1--;
l1min=min(l1,l1min);
r1max=max(r1max,r1);
} else if(a[i]=='D') {
l1++,r1++;
l1min=min(l1,l1min);
r1max=max(r1max,r1);
} else if(a[i]=='L') {
l2--,r2--;
l2min=min(l2,l2min);
r2max=max(r2max,r2);
} else {
l2++,r2++;
l2min=min(l2,l2min);
r2max=max(r2max,r2);
}
}
int x1=2-l1min,x2=n-(r1max-n),y1=2-l2min,y2=m-(r2max-m);
if(x1>x2||y1>y2) {
if(k) cout<<0<<"\n";
else cout<<n*m<<"\n";
} else {
int p=(x2-x1+1)*(y2-y1+1);
vector<vector<int>> d(n+10,vector<int>(m+10));
string s=a;
for(int i=0; i<s.size(); i++) {
d[x1][y1]++;
d[x2+1][y1]--;
d[x1][y2+1]--;
d[x2+1][y2+1]++;
if(s[i]=='U') x1--,x2--;
else if(s[i]=='D') x1++,x2++;
else if(s[i]=='L') y1--,y2--;
else y1++,y2++;
}
d[x1][y1]++;
d[x2+1][y1]--;
d[x1][y2+1]--;
d[x2+1][y2+1]++;
vector<vector<int>> c(n+10,vector<int>(m+10));
c[1][1]=d[1][1];
for(int i=2; i<=m; i++) c[1][i]=d[1][i]+c[1][i-1];
for(int i=2; i<=n; i++) c[i][1]=d[i][1]+c[i-1][1];
for(int i=2; i<=n; i++) {
for(int j=2; j<=m; j++) {
c[i][j]=d[i][j]+c[i-1][j]+c[i][j-1]-c[i-1][j-1];
}
}
int sum=0;
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
//cout<<c[i][j]<<" ";
if(c[i][j]==p-k) sum++;
}
//cout<<endl;
}
cout<<sum<<"\n";
}
}
signed main() {
int T=1;
cin>>T;
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
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: 3ms
memory: 3920kb
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 17 9 18 15 21 240 14 0 0 5 1 18 3 16 1 31 108 8 1 2 3 7 0 29 4 20 0 8 10 9 6 5 320 3 5 3 0 0 7 0 11 0 0 8 128 22 18 51 23 5 6 3 9 48 28 8 1 22 49 13 10 2 12 6 18 44 0 14 5 0 4 30 14 99 105 2 27 17 0 66 10 11 28 52 32 8 22 14 0 90 15 0 22 3 48 29 20 9 0 30 6 8 3 10 16 45 16 17 0 20 0 21 0 6 0 ...
result:
wrong answer 3rd numbers differ - expected: '20', found: '17'