QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89367#5414. Stop, Yesterday Please No Moreylf20010818#WA 1ms3596kbC++172.9kb2023-03-19 21:30:452023-03-19 21:30:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 21:30:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3596kb
  • [2023-03-19 21:30:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+10;

void solve(){

    int n,m,k;
    cin>>n>>m>>k;
    int dd=n*m;
    string s;
    cin>>s;
    int up=0,ri=0;
    int upm=-inf,upd=inf;
    int rim=-inf,rid=inf;
    for(int i=0;i<s.length();i++){

        char ch=s[i];
        if(s[i]=='U') up++;
        else if(s[i]=='D') up--;
        else if(s[i]=='R') ri--;
        else ri++;
        upm=max(upm,up);
        upd=min(upd,up);
        rim=max(rim,ri);
        rid=min(rid,ri);
    }
    n=n-abs(upm)-abs(upd);
    m=m-abs(rim)-abs(rid);
    if(n*m<=0&&k==0){

        cout<<dd<<"\n";
        return;
    } else if(n*m<=0&&k>0){

        cout<<0<<"\n";
        return;
    }
    int num=n*m-k;
    vector<vector<int>> a(abs(upm)+abs(upd)+50,vector<int>(abs(rim)+abs(rid)+50,0));
    int ix=abs(rid)+1;
    int iy=abs(upd)+1;
    int inx=ix,iny=iy;
    int ns=abs(upm)+abs(upd)+1;
    int ms=abs(rim)+abs(rid)+1;
    a[ix][iy]=1;
    for(int i=0;i<s.length();i++){

        if(s[i]=='U') iy++;
        else if(s[i]=='D') iy--;
        else if(s[i]=='R') ix--;
        else ix++; 
        a[iy][ix]=1;
    }
    // for(int i=1;i<=ns;i++){

    //     for(int j=1;j<=ms;j++){

    //         cout<<a[i][j];
    //     }
    //     cout<<"\n";
    // }
    for(int i=1;i<=ns;i++){

        for(int j=1;j<=ms;j++){

            a[i][j]+=a[i-1][j];
        }
    }

    for(int i=1;i<=ns;i++){

        for(int j=1;j<=ms;j++){

            a[i][j]+=a[i][j-1];
        }
    }
    // for(int i=1;i<=ns;i++){

    //     for(int j=1;j<=ms;j++){

    //         cout<<a[i][j];
    //     }
    //     cout<<"\n";
    // }
    n=n+abs(upm)+abs(upd);
    m=m+abs(rim)+abs(rid);
    // cout<<ns<<" "<<ms<<"\n";
    // cout<<iny<<" "<<inx<<"\n";
    int ans=0;
    // cout<<py<<" "<<px<<"\n";
    // cout<<1+upm<<" "<<1+rim<<"\n";
    // cout<<n+upd<<" "<<m+rid<<"\n";
    // cout<<num<<'\n';
    for(int i=1;i<=n;i++){

        for(int j=1;j<=m;j++){

            // if(ns+i-iny<1+upm||ms-inx+j<1+rim||i+1-iny>n+upd||j+1-inx>m+rid) continue;
            // cout<<i-iny+1<<" "<<j-inx+1<<" "<<ns+i-iny<<" "<<ms-inx+j<<"\n";
            // cout<<1+upm<<" "<<1+rim<<" "<<n+upd<<" "<<m+rid<<"\n";
            int n2=min(ns+i-iny,n+upd),m2=min(ms-inx+j,m+rid);
            int n1=max(1+i-iny,1+upm),m1=max(1+j-inx,1+rim);
            // cout<<i<<" "<<j<<"\n";
            // cout<<n2<<" "<<m2<<" "<<n1<<" "<<m1<<"\n";
            // int dy=n2-n1+1,dx=m2-m1+1;
            int py=i-iny+1,px=j-inx+1;
            int now=a[n2-py+1][m2-px+1]-a[n1-py][m2-px+1]-a[n2-py+1][m1-px]+a[n1-py][m1-px];
            // cout<<i<<" "<<j<<" "<<now<<"\n";
            if(now==num) ans++;
        }
    }
    cout<<ans<<"\n";
    a.clear();
}
int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){

        solve();
    }
}

详细

Test #1:

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

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: 1ms
memory: 3596kb

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:

21
11
4
99
15
15
0
240
0
0
0
0
8
18
0
0
1
19
0
0
2
0
10
0
0
30
16
0
0
13
10
9
15
7
320
11
2
5
0
0
7
0
4
0
0
9
0
22
0
51
0
8
6
4
2
48
28
8
7
0
0
17
0
4
0
10
0
44
0
15
2
0
4
30
1
0
105
10
26
17
0
66
0
11
28
0
0
56
0
0
56
90
14
0
121
0
48
8
36
13
0
30
7
0
3
11
0
0
0
34
0
38
0
34
0
5
0
0
27
48
9
3
225
0...

result:

wrong answer 1st numbers differ - expected: '228', found: '21'