QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229717 | #5414. Stop, Yesterday Please No More | mobbb# | WA | 0ms | 3748kb | C++17 | 3.0kb | 2023-10-28 16:43:45 | 2023-10-28 16:43:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,double> PLL;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
ll t;
ll n,m,k;
string str;
int main (void)
{
cin>>t;
while(t--)
{
cin>>n>>m>>k;
vector<vector<ll>> Map(n+2,vector<ll>(m+2,0));
cin>>str;
ll Len=str.size();
ll l=1,r=m,u=1,d=n;
ll Height=0,Width=0;
for(int i=0;i<Len;i++)
{
if(str[i]=='U')
Height--;
else if(str[i]=='L')
Width--;
else if(str[i]=='D')
Height++;
else if(str[i]=='R')
Width++;
if((u+Height)<1)
u++;
else if((d+Height)>n)
d--;
else if((l+Width)<1)
l++;
else if((r+Width)>m)
r--;
}
ll num=0;
if(l>r||u>d) {
num = 0;
if(k==0)
cout<<n*m<<endl;
else
cout<<"0\n";
}
else if(k>=n*m)
cout<<"0\n";
else {
num = (r - l + 1) * (d - u + 1);
// cout<<l<<" "<<r<<" "<<" "<<u<<" "<<d<<" "<<num<<endl;
Map[u][l] += 1;
Map[d + 1][l] -= 1;
Map[u][r + 1] -= 1;
Map[d + 1][r + 1] += 1;
for (int i = 0; i < Len; i++) {
// 经过一系列变化
if (str[i] == 'U') {
u--;
d--;
} else if (str[i] == 'L') {
l--;
r--;
} else if (str[i] == 'D') {
u++;
d++;
} else if (str[i] == 'R') {
l++;
r++;
}
// 左上角 (u,l) 右下角 (d,r)
// cout << l << " " << r << " " << " " << u << " " << d << endl;
Map[u][l] += 1;
Map[d + 1][l] -= 1;
Map[u][r + 1] -= 1;
Map[d + 1][r + 1] += 1;
}
ll ans = 0;
// cout << num << " " << k << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
Map[i][j] += Map[i - 1][j] + Map[i][j - 1] - Map[i - 1][j - 1];
// cout << Map[i][j] << " ";
if (Map[i][j] == (num - k))
ans++;
}
// cout << endl;
}
cout << ans << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
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: 0ms
memory: 3748kb
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'