QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#503994#5414. Stop, Yesterday Please No MorevwxyzAC ✓26ms15116kbC++232.5kb2024-08-04 03:41:482024-08-04 03:41:54

Judging History

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

  • [2024-08-04 03:41:54]
  • 评测
  • 测评结果:AC
  • 用时:26ms
  • 内存:15116kb
  • [2024-08-04 03:41:48]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to compute cumulative sum
int cumsum(const vector<vector<int>>& C, int a, int b, int c, int d) {
    if (a >= b || c >= d) {
        return 0;
    }
    return C[b][d] + C[a][c] - C[a][d] - C[b][c];
}

int main() {
    int T;
    cin >> T;
    
    while (T--) {
        int N, M, K;
        cin >> N >> M >> K;
        
        string S;
        cin >> S;
        
        int le = S.length();
        int x0 = 0, x1 = N;
        int y0 = 0, y1 = M;
        int x = 0, y = 0;
        
        vector<int> X = {x}, Y = {y};
        
        for (char s : S) {
            if (s == 'U') {
                x -= 1;
            } else if (s == 'D') {
                x += 1;
            } else if (s == 'R') {
                y -= 1;
            } else if (s == 'L') {
                y += 1;
            }
            x0 = max(x0, x);
            x1 = min(x1, N + x);
            y0 = max(y0, y);
            y1 = min(y1, M + y);
            X.push_back(x);
            Y.push_back(y);
        }
        
        x1 = max(x1, x0);
        y1 = max(y1, y0);
        
        int minX = *min_element(X.begin(), X.end());
        int minY = *min_element(Y.begin(), Y.end());
        
        for (int i = 0; i <= le; ++i) {
            X[i] -= minX;
            Y[i] -= minY;
        }
        
        int leX = *max_element(X.begin(), X.end()) + 1;
        int leY = *max_element(Y.begin(), Y.end()) + 1;
        
        vector<vector<int>> C(leX + 1, vector<int>(leY + 1, 0));
        
        for (int i = 0; i <= le; ++i) {
            C[X[i] + 1][Y[i] + 1] = 1;
        }
        
        for (int i = 0; i <= leX; ++i) {
            for (int j = 1; j <= leY; ++j) {
                C[i][j] += C[i][j - 1];
            }
        }
        
        for (int i = 1; i <= leX; ++i) {
            for (int j = 0; j <= leY; ++j) {
                C[i][j] += C[i - 1][j];
            }
        }
        
        int ans = 0;
        for (int x = 0; x < N; ++x) {
            for (int y = 0; y < M; ++y) {
                int dx = x - X[0], dy = y - Y[0];
                if ((x1 - x0) * (y1 - y0) == K + cumsum(C, max(0, x0 - dx), min(leX, x1 - dx), max(0, y0 - dy), min(leY, y1 - dy))) {
                    ans += 1;
                }
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 3652kb

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: 2ms
memory: 3800kb

input:

1
1000 1000 979065
DDUULULUDULLULLDLUULURRLDURLRDLRRUURUUUDLRLUUDUUDUDLLDDDULU

output:

958416

result:

ok 1 number(s): "958416"

Test #4:

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

input:

1
1000 1000 943471
LRLDLURLDLRDRDUULULRDDLLRURDUURLLDDLDLDDLLLUUURLDRUDRLLUUUUUDLUUDLURURRDLRLRRRLULRRULURLRRDLDRLUDRRLDDLUDRRLLUDLLLRDULRRRRLDUUDRDLULUUUUDRRDULUDLLUUDLDURDRRLRRLDRLDDRURURLUULRRLDLLRLRDRRUULDLDLULLDLLRULLRUULURDURRLUUDUULLULDLRUDDLRLRLLUDDDLLLUDRRLDDULRRURRDURDDRDLLULRLULURLRDLLURD...

output:

889224

result:

ok 1 number(s): "889224"

Test #5:

score: 0
Accepted
time: 26ms
memory: 13224kb

input:

1
1000 1000 315808
LLRURURRDDDULLDDUDRDLRLLLDDDLUDRDURLDULRLRULUUDLUULUUDULLLLDDURLDUULUUDLLDLLDRUDUULRLLRLRUURLRLULLDDLLDUDLLRUUDRLDLUULDLLDRRRURDULLDRRRDURURDRLDURURUDLURLDURRLRRUDUDURDRLRRRDLRRURLURUDRRLDLRULLDLUURDURLURLLRDLRDRUURURDRUDUUUDLRRLUDLUUDUDDRRDUULUUDDRLLULDUUDRURRDRLULRLULDURLURUDLLD...

output:

426

result:

ok 1 number(s): "426"

Test #6:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

1
1000 1000 986018
LLULDRRRDDURRUDRUURRRDDLUUDUULRULRDULLD

output:

972180

result:

ok 1 number(s): "972180"

Test #7:

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

input:

1
1000 1000 945431
DDRRURUUDLDULLDLDDLRULDLLDDRRLUDRLUURRLDRDLURUURRRRLRURLURULLLDRDDDRRRLDLDRLRDDUURRURDDDLRUURLUURLRDUDDDLLDUURLDLUDLLRRDUUDRLUULLUULDLURRUDLUURLRLRURDUDRRRDRLRUDLLLLURLULRLRLRRDDUDLRLDUUUULUDLLURRLURRDLRURRRULDDLLLRLRDLUDLLDDRULDUULRDDUUDDUDLURDULLDUDDLULRULDRLDDULDULLUDLULUDRURRR...

output:

893000

result:

ok 1 number(s): "893000"

Test #8:

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

input:

1
1000 1000 460035
RDDUURDULDDLDDLDDLDRRULLRLUURLURRRDRUDDDRDLDLDULUDLRLLRRLRRURRRDLRLUDRDURULDRRDDDDDDLRLDULUULDUDRLLUUUURUUDRURLRRULDRDRUUUUULULRURDDRLRULLLRDRRULUDDUDDLLLRDRUULUUDDRLURDLDURRDLRRLDRRUDLUULRDLURULLDLRLLDDURDUDLDULDLLRULRDLRLUULLUDRUDDDLRRDULULLRUURLUURRLLLLRLDRURLLRLDRRDDDRLUUUUDUL...

output:

417

result:

ok 1 number(s): "417"

Test #9:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

1
1000 1000 992010
LLLLLDLDRRLUDRR

output:

1999

result:

ok 1 number(s): "1999"

Test #10:

score: 0
Accepted
time: 2ms
memory: 3816kb

input:

1
1000 1000 919600
LLDLRUDRLURRUDRDRRDLRUDLRRRUUULDLDURDDDRUURRRLLURULDRLRLULLULDRULULRLRRRURLDDDRUUULUDLLLLRRLLRDDRDULUDLRLRLDRLUDUDURRULUULLDULUULDLLDRDULUDLDULDDUULDDRRURDRDULRRLDRRDUURURRLUUUDRRLDRRDDLULRDDLDLLRLRLLLRULUUUURRRLDLRUDRRLRURDRLDULLLUDRULLDLDRRUUDLRRLLRLDDLUDLRLRRURUUDUULUDURDURRLUU...

output:

944

result:

ok 1 number(s): "944"

Test #11:

score: 0
Accepted
time: 26ms
memory: 15116kb

input:

1
1000 1000 804351
DLRLDLLLLUDRDURRLDDRRLRUULURURDDDRDLRUDDULRRLLULURDRUUDRURRLURRRDRURRDRLULRDLRRDRRDDUDLUDLDULRUURRLRUUDRLDDRDDUUDULUULUUUDLRURULLRDUUDDDRRLDRUDDUUDRURLRDRUDLRLDDRRLLRLRDUDDULLULRLLDDUDDDUULDULLRRULULDUUULUDRRDRLUDLRRDDUDLRRDDLDLDRUULRRRRRLRLULLRDDRDDDULDRRURUDDLURLRLURLRDRULUDULUU...

output:

640000

result:

ok 1 number(s): "640000"