QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#401391#5414. Stop, Yesterday Please No MoredukerAC ✓105ms16328kbC++202.9kb2024-04-28 16:41:352024-04-28 16:41:36

Judging History

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

  • [2024-04-28 16:41:36]
  • 评测
  • 测评结果:AC
  • 用时:105ms
  • 内存:16328kb
  • [2024-04-28 16:41:35]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS 0
#include <iostream> 
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<set>
#include<queue>
#include <stack>
#include<list>
#include<cstring>
#include<cmath>
#include <cstdlib>
#include<fstream>
#include<climits>
using namespace std;
int divs[1005][1005];
int sum[1005][1005];
void solve() {
    int n, m, up = 0, down = 0, left = 0, right = 0;
    int k;
    scanf("%d %d %d", &n, &m, &k);
    int height = n, width = m;
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++)
    {
        if (str[i] == 'U') {
            if (up == 0) {
                height--;
            }
            else {
                up--;
            }
            down++;
        }
        else if(str[i] == 'D'){
            if (down == 0) {
                height--;
            }
            else {
                down--;
            }
            up++;
        }
        else if (str[i] == 'L') {
            if (left == 0) {
                width--;
            }
            else {
                left--;
            }
            right++;
        }
        else {
            if (right == 0) {
                width--;
            }
            else {
                right--;
            }
            left++;
        }
    }
    //开始差分
    int x = up + 1, y = left + 1;
    height = max(height, 0);
    width = max(width, 0);
    set<pair<int, int>> st;
    for (int i = str.size() - 1; i >=0 ; i--)
    {
        if (st.find({ x , y }) == st.end()) {
            st.insert({ x,y });
            divs[x][y]++; 
            divs[x + height][y]--;
            divs[x][y + width]--;
            divs[x + height][y + width]++;
        }
        if (str[i] == 'U') {
            x++;
        }
        else if (str[i] == 'D') {
            x--;
        }
        else if (str[i] == 'L') {
            y++;
        }
        else {
            y--;
        }
    }
    if (st.find({ x , y }) == st.end()) {
        st.insert({ x,y });
        divs[x][y]++;
        divs[x + height][y]--;
        divs[x][y + width]--;
        divs[x + height][y + width]++;
    }
    int ans = 0;
    for (int i =  1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            divs[i][j] += divs[i - 1][j] + divs[i][j - 1] - divs[i - 1][j - 1];
            //cout << divs[i][j] << " ";
            if (height * width - k == divs[i][j]) {
                ans++;
            }
        }
        //cout << endl;
    }
    printf("%d\n", ans);
    for (int i = 1; i <= n+ 1; i++)
    {
        for (int j = 1; j <= m+1; j++)
        {
            divs[i][j] = 0;
            sum[i][j] = 0;
        }
    }
}
int main() {
   
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 9ms
memory: 10072kb

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: 0ms
memory: 11648kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

score: 0
Accepted
time: 0ms
memory: 11688kb

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 105ms
memory: 16328kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 0ms
memory: 11932kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

score: 0
Accepted
time: 4ms
memory: 11740kb

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

score: 0
Accepted
time: 88ms
memory: 14372kb

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 0ms
memory: 11900kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 4ms
memory: 11764kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 75ms
memory: 12552kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"