QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#251909#5414. Stop, Yesterday Please No MoreTimMCBenAC ✓29ms9524kbC++204.5kb2023-11-15 12:35:032023-11-15 12:35:03

Judging History

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

  • [2023-11-15 12:35:03]
  • 评测
  • 测评结果：AC
  • 用时：29ms
  • 内存：9524kb
查看
  • [2023-11-15 12:35:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
int main()
{
    /* IOS; */
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        string s;
        cin>>s;
        vector<int>a,b;
/*         for(auto &it:s)
        {
            if(it=='U') it='D';
            else if(it=='D') it='U';
        } */
        for(auto it:s)
        {
            if(it=='U'||it=='D')
            {
                a.push_back(it);
            }else
            {
                b.push_back(it);
            }
        }
        int pre=0;
        int u=0,d=0;
        for(auto it:a)
        {
            if(it=='D')
            {
                //上边界往下move距离
                pre++;
            }else
            {
                //下边界往上move距离
                pre--;
            }
            u=max(u,pre);
            d=max(d,-pre);
        }
        int U = 1 + d ;
        int D = n - u ;

        pre=0;
        int l=0,r=0;
        for(auto it:b)
        {
            if(it=='R')
            {
                //左边界往右move距离
                pre++;
            }else
            {
                //右边界往左move距离
                pre--;
            }
            l=max(l,pre);
            r=max(r,-pre);
        }
        int L = 1 + r;
        int R = m - l;
        /* cout<<U<<" "<<D<<" "<<L<<" "<<R<<endl; */
/*         for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i>=U&&i<=D&&j>=L&&j<=R)
                {
                    cout<<1;
                }else
                {
                    cout<<0;
                }
            }
            cout<<endl;
        } */
        if(L>R||U>D)
        {
            if(k==0)
            {
                cout<<n*m<<endl;
            }else
            {
                cout<<0<<endl;
            }
            continue;
        }

        int len = u + d + 1;
        int wid = l + r + 1;

        vector<vector<int>>v(len+1,vector<int>(wid+1));

        int x = len - d, y = wid - r;
        
        v[x][y]=1;
        /* cout<< x<<" "<< y<<endl; */
        for(auto it:s)
        {
            if(it=='U') x++;
            else if(it=='D') x--;
            else if(it=='L') y++;
            else if(it=='R') y--;
            v[x][y] = 1;
        }
/*         for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                cout<<v[i][j]<<" ";
            }
            cout<<endl;
        } */

        vector<vector<int>>pr=v;
        for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                pr[i][j]=pr[i][j]+pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1];
            }
        }

/*         for(int i=1;i<=len;i++)
        {
            for(int j=1;j<=wid;j++)
            {
                cout<<pr[i][j];
            }
            cout<<endl;
        }  */       
        int ans = (R - L +1)*(D - U +1);
        /* cout<<ans<<endl; */
        int res = 0;
        //枚举原矩形的右下角的位置
        for(int i=1;i<=n + d;i++)
        {
            for(int j=1;j<=m + r;j++)
            {
                int x_d = min(D , i);
                int x_u = max(U , i - len +1);

                int x_r = min(R , j);
                int x_l = max(L , j - wid +1);

/*                 if(i-d==4&&j-r==2)
                {
                    cout<<"gg"<<endl;
                    cout<<x_u<<" "<<x_d<<endl;
                    cout<<x_l<<" "<<x_r<<endl;
                } */


                if(x_u > x_d) continue;
                if(x_l > x_r) continue;

                int x = len - (i-x_d);
                int y = wid - (j-x_r);

                int w = len - (i-x_u);
                int z = wid - (j-x_l); 

                if(i-d>=1&&i-d<=n&&j-r>=1&&j-r<=m)
                {
                    if(ans-(pr[x][y]-pr[x][z-1]-pr[w-1][y]+pr[w-1][z-1])==k)
                    {
                        res++;
                     }
                   /* cout<< x<<" "<<y<<" "<<w<<" "<<z<<endl; */
                   /* cout<<pr[x][y]-pr[x][z-1]-pr[w-1][y]+pr[w-1][z-1]<<endl; */
                }             
                  
            }

        }
        cout<<res<<endl;
    }
}
/*
3
4 5 3
ULDDRR
4 5 0
UUUUUUU
4 5 10
UUUUUU
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3416kb

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: 0
Accepted
time: 3ms
memory: 3588kb

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
34
240
15
0
0
13
14
18
26
16
1
19
108
8
2
2
3
7
0
30
16
21
0
8
10
9
15
5
320
11
7
3
0
0
12
0
11
0
0
14
0
22
36
51
23
7
6
4
2
48
28
8
63
22
49
13
10
4
108
10
18
44
0
15
9
0
4
30
14
99
105
10
14
17
0
66
10
11
28
52
34
56
33
14
56
90
14
0
121
3
48
30
36
13
0
30
7
8
3
11
16
45
20
34
0...

result:

ok 1060 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 3444kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 3ms
memory: 3488kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 29ms
memory: 9404kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 3ms
memory: 3392kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 5ms
memory: 3500kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 24ms
memory: 9524kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 3ms
memory: 3468kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 3ms
memory: 3392kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 25ms
memory: 9456kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"
English 繁體中文 简体中文

Server Time: 2024-12-02 15:47:51 | OpenSource Project