QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#705664#5414. Stop, Yesterday Please No MoreHanoistWA 6ms11104kbC++142.2kb2024-11-03 00:22:092024-11-03 00:22:10

Judging History

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

  • [2024-11-03 00:22:10]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:11104kb
  • [2024-11-03 00:22:09]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<utility>
#include<cassert>
using namespace std;
inline int read(){
    int x = 0,f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
const int N = 1e3 + 11;
int n,m,k;
char s[N * N];
int a[3 * N][3 * N],sum[3 * N][3 * N];
inline int calc(int x,int y,int xx,int yy){
    return sum[xx][yy] - sum[x - 1][yy] - sum[xx][y - 1] + sum[x - 1][y - 1];
}
int main(){
    int t,i,j,k,x,y,z;
    t = read();
    while(t--){
        n = read(),m = read(),k = read();
        scanf(" %s",s + 1);
        int p = strlen(s + 1);
        x = 0,y = 0;
        int L = 0,R = 0,U = 0,D = 0;
        for(i = 1;i <= p;i++){
            if(s[i] == 'L') --x,L = min(L,x);
            if(s[i] == 'R') ++x,R = max(R,x);
            if(s[i] == 'U') --y,U = min(U,y);
            if(s[i] == 'D') ++y,D = max(D,y);
        }
        L = -L,U = -U;
        if(L + R >= m || U + D >= n){
            if(!k) printf("%d\n",n * m);
            else puts("0");
            continue;
        }
        for(i = 1;i <= 3 * n;i++){
            for(j = 1;j <= 3 * m;j++){
                a[i][j] = 0;
            }
        }
        int sx,sy;
        sx = x = n,sy = y = m;
        a[sx][sy] = 1;
        for(i = 1;i <= p;i++){
            if(s[i] == 'L') --y;
            if(s[i] == 'R') ++y;
            if(s[i] == 'U') --x;
            if(s[i] == 'D') ++x;
            a[x][y] = 1;
        }
        for(i = 1;i <= 3 * n;i++){
            for(j = 1;j <= 3 * m;j++){
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
            }
        }
        int res = 0;
        for(i = sx;i > sx - n;i--){
            for(j = sy;j > sy - m;j--){
                int u = i + U,v = j + L;
                if(calc(u,v,i + n - 1 - D,j + m - 1 - R) == k) ++res;
            }
        }
        printf("%d\n",res);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 6ms
memory: 11104kb

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
0
0
0
18
0
0
0
0
0
0
1
1
3
0
0
0
0
0
0
0
0
9
2
0
320
0
0
3
0
0
0
0
0
0
0
0
0
22
0
51
0
6
6
0
0
48
28
8
0
0
0
0
0
0
0
0
0
44
0
0
0
0
4
30
0
0
105
0
0
17
0
66
0
11
28
0
0
0
0
0
0
90
0
0
0
1
48
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
0
0
225
0
0
0
0
11
0
90
0
0
228
0
3...

result:

wrong answer 3rd numbers differ - expected: '20', found: '0'