QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#725055#5414. Stop, Yesterday Please No MorehelloccclTL 6ms36060kbC++202.8kb2024-11-08 16:04:122024-11-08 16:04:12

Judging History

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

  • [2024-11-08 16:04:12]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:36060kb
  • [2024-11-08 16:04:12]
  • 提交

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()
{



    for(int i = 0;i<=2004;i++)
    {
        for(int j = 0;j<=2004;j++)
        {
            mp[i][j] = 1;
        }
    }

    maxu= 0;maxd=0;
    maxl= 0;maxr=0;
    cin >> n >> m >> k;
    char s[1000005];
    cin >> s;
    int len = strlen(s);


    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);
    if(wide <=0||high <=0)
    {
        if(k == 0)
            {
                cout << n * m <<'\n';
                return;
            }
    }



//cout << high  <<' ' <<wide<< '\n';

    int x = m ;
    int y = n ;
    mp[x][y] = 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[x][y] = 0;
    }

    for(int i = 1;i<=2004;i++)
    {
        for(int j = 1;j<=2004;j++)
        {
            sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mp[i][j];
        }
    }
    //cout << sum[2][2]<<'\n';
    int ans = 0;

    for(int i = 1;i<=m ;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            int temp =0;
            /*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 + 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];
            if(temp == k)
            {
                ans ++;
            }
            //cout << temp << '\n';
        }
    }


    cout << ans << '\n';




}

int main()
{
    int  _;
    cin >> _;
    while (_--)
    {
        solve();
    }

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 36060kb

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
Time Limit Exceeded

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
0
0
0
15
0
240
0
0
1
3
0
18
0
0
0
0
0
7
1
1
0
0
0
0
0
0
0
0
0
9
0
5
320
0
0
5
0
0
8
0
0
0
0
0
0
22
0
51
0
0
6
1
0
48
28
8
0
11
65
1
0
0
0
0
0
44
0
0
0
0
4
30
13
99
105
0
0
17
0
66
0
11
28
52
0
64
11
0
56
90
0
0
0
1
48
0
0
0
0
30
0
4
0
0
16
45
2
18
0
0
0
0
0
0
0
24
0
48
3
0
225
0
0
0
0
11
19
9...

result: