QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#180506#5414. Stop, Yesterday Please No MoreZhou_JKWA 4ms10304kbC++232.1kb2023-09-15 22:05:322023-09-15 22:05:33

Judging History

你现在查看的是最新测评结果

  • [2023-09-15 22:05:33]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:10304kb
  • [2023-09-15 22:05:32]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1005,L=1000005;
int n,m,k;
int len;
char s[L];
int a[N][N],sum[N][N];
int getsum(int l1,int r1,int l2,int r2)
{
    l1=max(l1,1),r1=max(r1,1),l2=min(l2,n),r2=min(r2,m);
    return sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1];
}
void solve()
{
    cin>>n>>m>>k;
    string str;
    cin>>str;
    len=str.size();
    for(int i=1;i<=len;i++)
        s[i]=str[i-1];
    int u=1,d=n,l=1,r=m;
    int curu=1,curd=n,curl=1,curr=m;
    for(int i=1;i<=len;i++)
    {
        if(s[i]=='U') curu++,curd++;
        else if(s[i]=='D') curu--,curd--;
        else if(s[i]=='L') curl++,curr++;
        else if(s[i]=='R') curr--,curl--;
        u=max(u,curu),d=min(d,curd),l=max(l,curl),r=min(r,curr);
    }
    if(u>d||l>r)
    {
        if(k==0) printf("%d\n",n*m);
        else printf("0\n");
        return;
    }
    int mnx=0,mny=0;
    int curx=0,cury=0;
    vector<pair<int,int>>pos;
    pos.emplace_back(curx,cury);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='U') curx--;
        else if(s[i]=='D') curx++;
        else if(s[i]=='L') cury++;
        else if(s[i]=='R') cury--;
        if(abs(curx)<d-u+1&&abs(cury)<r-l+1) pos.emplace_back(curx,cury);
        mnx=min(mnx,curx),mny=min(mny,cury);
    }
    mnx=-mnx,mny=-mny;
    mnx++,mny++;
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    for(auto &[x,y]:pos)
        x+=mnx,y+=mny;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=0;
    for(auto [x,y]:pos)
        a[x][y]++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    int ans=0;
    for(int i=u;i<=d;i++)
        for(int j=l;j<=r;j++)
            if(getsum(mnx-(i-u),mny-(j-l),mnx+(d-i),mny+(r-j))==(d-u+1)*(r-l+1)-k) ans++;
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7880kb

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: 4ms
memory: 10304kb

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:

1
1
7
0
6
0
0
1
7
0
0
0
14
9
4
1
1
2
0
0
0
2
4
0
7
10
2
5
8
0
0
0
24
3
0
11
10
0
6
14
1
12
0
1
2
0
1
1
13
4
2
0
0
9
1
8
0
1
11
5
1
0
8
13
15
0
11
5
7
1
0
12
0
1
16
1
0
2
7
20
2
0
5
1
1
0
19
0
2
0
0
0
10
12
0
7
14
80
7
2
3
13
14
0
0
3
1
4
12
0
0
0
1
14
1
11
0
10
8
0
12
13
0
0
0
1
78
2
0
0
1
3
0
13
10...

result:

wrong answer 1st numbers differ - expected: '228', found: '1'