QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#725516 | #5414. Stop, Yesterday Please No More | hellocccl | WA | 8ms | 7560kb | C++20 | 4.0kb | 2024-11-08 18:27:46 | 2024-11-08 18:27:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int mp[2005][2005];
int n,m,k;
int maxu,maxd;
int maxl,maxr;
int sum[2005][2005];
void solve()
{
maxu= 0;maxd=0;
maxl= 0;maxr=0;
cin >> n >> m >> k;
char s[1000005];
cin >> s;
int len = strlen(s);
for(int i = 0;i<=2*n+5;i++)
{
for(int j = 0;j<=2*m+5;j++)
{
mp[i][j] = 1;
}
}
int tempup = 0;
int templr = 0;
for(int i = 0;i<len;i++)
{
if(s[i]=='U')
{
tempup ++;
maxu = max(maxu,tempup);
maxd = min(maxd,tempup);
}
if(s[i]=='D')
{
tempup --;
maxu = max(maxu,tempup);
maxd = min(maxd,tempup);
}
if(s[i]=='L')
{
templr --;
maxl = min(templr,maxl);
maxr = max(templr,maxd);
}
if(s[i]=='R')
{
templr ++;
maxl = min(templr,maxl);
maxr = max(templr,maxd);
}
}
//maxl,maxr,maxd,maxu;
int wide ;int high;
wide = m - maxr - abs(maxl);
high = n - maxu - abs(maxd);
//cout << high <<' ' <<wide<< '\n';
if(wide <=0||high <=0)
{
if(k == 0)
{
cout << n * m <<'\n';
return;
}
}
int x = m ;
int y = n ;
mp[y][x] = 0;
for(int i = 0;i<len;i++)
{
if(s[i]=='U')
{
y ++;
}
if(s[i]=='D')
{
y--;
}
if(s[i]=='L')
{
x++;
}
if(s[i]=='R')
{
x--;
}
mp[y][x] = 0;
}
// for(int i = 0;i<=2*n+5;i++)
// {
// for(int j = 0;j<=2*m+5;j++)
// {
// cout <<mp[i][j]<<' ';
// }
// cout << '\n';
// }
for(int i = 1;i<=2*n;i++)
{
for(int j = 1;j<=2*m;j++)
{
sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
//cout <<sum[i][j]<<' ';
}
//cout << '\n';
}
// for(int i = 1;i<=2*n;i++)
// {
// for(int j = 1;j<=2*m;j++)
// {
// sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
// cout <<sum[i][j]<<' ';
// }
// cout << '\n';
// }
int ans = 0;
// cout<<maxl<<" "<<maxr<<'\n';
for(int i = 1;i<=n ;i++)
{
for(int j = 1;j<=m;j++)
{
int temp =0;
//cout << j + wide +abs(maxr) - 1 <<' ' <<i + high + abs(maxu)-1<<'\n';
/*cout << sum[i + wide + abs(maxl)-1][j+high + abs(maxu) -1]<<' '
<< sum[i + abs(maxl) - 1][j+high + abs(maxu) -1] <<' '<< sum[j + abs(maxu)-1][i + wide + abs(maxl)-1] <<' '<< sum[i + abs(maxl) - 1][j + abs(maxu)-1] <<'\n';*/
temp = sum[i + high + abs(maxu)-1][j+wide + abs(maxl) -1]
-sum[i + abs(maxu) - 1][j+wide + abs(maxl) -1]
- sum[i + high+ abs(maxu)-1][j + abs(maxl)-1]
+ sum[i + abs(maxu) - 1][j + abs(maxl)-1];
// cout << temp << '\n' <<'\n';
if(temp == k)
{
// cout << j + wide +abs(maxr) - 1 <<' ' <<i + high + abs(maxu)-1<<'\n';
// cout <<j + abs(maxr)-1<<' '<< i + abs(maxu) - 1 << '\n';
// cout << sum[i + high + abs(maxu)-1][j+wide + abs(maxr) -1] <<'\n';
// cout <<sum[i + abs(maxu) - 1][j+wide + abs(maxr) -1] <<'\n';
// cout << sum[j + abs(maxr)-1][i + high+ abs(maxu)-1] <<'\n';
// cout << sum[i + abs(maxu) - 1][j + abs(maxr)-1]<<'\n';
ans ++;
}
//cout << temp << '\n';
}
}
cout << ans << '\n';
}
int main()
{
int _;
cin >> _;
while (_--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6616kb
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: 8ms
memory: 7560kb
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 0 0 15 0 20 13 0 18 0 16 1 2 0 8 2 2 0 7 0 30 60 21 0 0 0 9 13 5 320 11 5 3 0 0 0 0 11 0 0 0 0 22 0 51 0 0 6 4 0 48 28 8 0 22 49 13 10 4 0 10 18 9 0 0 9 0 4 30 14 99 105 10 14 17 0 0 8 11 28 52 60 56 33 0 56 0 0 0 0 3 48 36 36 0 0 30 1 8 0 0 16 45 0 34 0 38 0 15 0 22 0 20 0 48 0 0...
result:
wrong answer 7th numbers differ - expected: '34', found: '0'