QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#611417#7781. Sheep Eat WolveswzxtslAC ✓46ms4596kbC++231.8kb2024-10-04 20:56:562024-10-04 20:56:58

Judging History

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

  • [2024-10-04 20:56:58]
  • 评测
  • 测评结果:AC
  • 用时:46ms
  • 内存:4596kb
  • [2024-10-04 20:56:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define For(i,j,k) for (int i=(j);i<=(k);i++)
#define rof(i,j,k) for (int i=(j);i>=(k);i--)
#define ull unsigned long long
#define lowbit(x) ((x)&(-(x)))
#define PII pair<int,int>
#define int long long
#define endl "\n"
#define ls rt<<1
#define rs rt<<1|1
typedef long long ll;
const int mod = 998244353;
const double eps = 1e-9;
const int N=207;
int n,m,p,q;
int a[N];
int ans=0x3f3f3f3f;
struct node{
    int sh;
    int wol;
    int no;
};
queue<node> Q;
int dp[207][207][2];
void solve(){
	cin>>n>>m>>p>>q;
    Q.push({n,m,0});
    memset(dp,-1,sizeof dp);
    dp[n][m][0]=0;
    while(!Q.empty()){
        int sh=Q.front().sh;
        int wl=Q.front().wol;
        int no=Q.front().no;
        Q.pop();
        if(no==0){
            for(int i=0;i<=sh;i++){
                for(int j=0;j<=wl;j++){
                    if((i+j)<=p&&dp[sh-i][wl-j][1]==-1&&((sh-i+q)>=(wl-j)||sh-i==0)){
                        dp[sh-i][wl-j][1]=dp[sh][wl][0]+1;
                        Q.push({sh-i,wl-j,1});
                    }
                }
            }
        }else{
            for(int i=0;i<=n-sh;i++){
                for(int j=0;j<=m-wl;j++){
                    if((i+j)<=p&&dp[sh+i][wl+j][0]==-1&&((n-sh-i+q)>=(m-wl-j)||(n-sh-i)==0)){
                        dp[sh+i][wl+j][0]=dp[sh][wl][1]+1;
                        Q.push({sh+i,wl+j,0});
                    }
                }
            }
        }
    }
    for(int i=0;i<=m;i++){
        if(dp[0][i][1]<ans&&dp[0][i][1]!=-1) ans=dp[0][i][1];
    }
    if(ans==0x3f3f3f3f) cout<<"-1"<<endl;
    else cout<<ans<<endl;
}
signed main(){
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4232kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 1ms
memory: 4484kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 1ms
memory: 4260kb

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 4484kb

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 0
Accepted
time: 1ms
memory: 4244kb

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 4248kb

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

score: 0
Accepted
time: 1ms
memory: 4268kb

input:

15 20 2 5

output:

27

result:

ok 1 number(s): "27"

Test #9:

score: 0
Accepted
time: 1ms
memory: 4256kb

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

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

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

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

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

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

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

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

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 5ms
memory: 4492kb

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: 0
Accepted
time: 5ms
memory: 4280kb

input:

60 60 16 16

output:

11

result:

ok 1 number(s): "11"

Test #16:

score: 0
Accepted
time: 6ms
memory: 4152kb

input:

60 60 16 24

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

75 15 1 1

output:

175

result:

ok 1 number(s): "175"

Test #18:

score: 0
Accepted
time: 1ms
memory: 4244kb

input:

50 100 1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 11ms
memory: 4280kb

input:

100 100 10 10

output:

35

result:

ok 1 number(s): "35"

Test #20:

score: 0
Accepted
time: 8ms
memory: 4252kb

input:

100 100 10 1

output:

37

result:

ok 1 number(s): "37"

Test #21:

score: 0
Accepted
time: 21ms
memory: 4280kb

input:

100 100 10 20

output:

33

result:

ok 1 number(s): "33"

Test #22:

score: 0
Accepted
time: 22ms
memory: 4196kb

input:

100 100 10 30

output:

31

result:

ok 1 number(s): "31"

Test #23:

score: 0
Accepted
time: 36ms
memory: 4460kb

input:

100 100 10 80

output:

21

result:

ok 1 number(s): "21"

Test #24:

score: 0
Accepted
time: 34ms
memory: 4480kb

input:

100 100 1 100

output:

199

result:

ok 1 number(s): "199"

Test #25:

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

input:

100 100 5 0

output:

95

result:

ok 1 number(s): "95"

Test #26:

score: 0
Accepted
time: 19ms
memory: 4508kb

input:

100 100 25 3

output:

13

result:

ok 1 number(s): "13"

Test #27:

score: 0
Accepted
time: 22ms
memory: 4312kb

input:

100 100 30 4

output:

11

result:

ok 1 number(s): "11"

Test #28:

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

input:

95 100 3 3

output:

125

result:

ok 1 number(s): "125"

Test #29:

score: 0
Accepted
time: 29ms
memory: 4312kb

input:

98 99 50 6

output:

5

result:

ok 1 number(s): "5"

Test #30:

score: 0
Accepted
time: 30ms
memory: 4540kb

input:

100 100 45 4

output:

7

result:

ok 1 number(s): "7"

Test #31:

score: 0
Accepted
time: 41ms
memory: 4252kb

input:

100 100 40 39

output:

7

result:

ok 1 number(s): "7"

Test #32:

score: 0
Accepted
time: 36ms
memory: 4300kb

input:

100 100 45 19

output:

7

result:

ok 1 number(s): "7"

Test #33:

score: 0
Accepted
time: 45ms
memory: 4236kb

input:

100 100 49 99

output:

5

result:

ok 1 number(s): "5"

Test #34:

score: 0
Accepted
time: 42ms
memory: 4376kb

input:

100 100 49 100

output:

5

result:

ok 1 number(s): "5"

Test #35:

score: 0
Accepted
time: 42ms
memory: 4596kb

input:

100 100 49 98

output:

5

result:

ok 1 number(s): "5"

Test #36:

score: 0
Accepted
time: 45ms
memory: 4380kb

input:

100 100 49 97

output:

5

result:

ok 1 number(s): "5"

Test #37:

score: 0
Accepted
time: 46ms
memory: 4380kb

input:

100 100 49 96

output:

5

result:

ok 1 number(s): "5"

Test #38:

score: 0
Accepted
time: 46ms
memory: 4368kb

input:

100 100 49 95

output:

5

result:

ok 1 number(s): "5"

Test #39:

score: 0
Accepted
time: 33ms
memory: 4232kb

input:

100 100 100 0

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 1ms
memory: 4268kb

input:

1 100 1 0

output:

1

result:

ok 1 number(s): "1"

Test #41:

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

input:

90 100 5 5

output:

87

result:

ok 1 number(s): "87"

Test #42:

score: 0
Accepted
time: 1ms
memory: 4408kb

input:

100 1 1 0

output:

199

result:

ok 1 number(s): "199"

Test #43:

score: 0
Accepted
time: 11ms
memory: 4280kb

input:

94 61 22 35

output:

9

result:

ok 1 number(s): "9"

Test #44:

score: 0
Accepted
time: 8ms
memory: 4440kb

input:

61 92 36 6

output:

7

result:

ok 1 number(s): "7"

Test #45:

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

input:

73 89 12 4

output:

57

result:

ok 1 number(s): "57"

Test #46:

score: 0
Accepted
time: 1ms
memory: 4188kb

input:

71 80 4 3

output:

-1

result:

ok 1 number(s): "-1"

Test #47:

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

input:

44 75 2 31

output:

85

result:

ok 1 number(s): "85"

Test #48:

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

input:

48 62 5 18

output:

35

result:

ok 1 number(s): "35"

Test #49:

score: 0
Accepted
time: 17ms
memory: 4220kb

input:

73 100 22 49

output:

9

result:

ok 1 number(s): "9"

Extra Test:

score: 0
Extra Test Passed