QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#768916#7781. Sheep Eat Wolvesguodong#TL 0ms3756kbC++171.3kb2024-11-21 15:13:052024-11-21 15:13:05

Judging History

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

  • [2024-11-21 15:13:05]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3756kb
  • [2024-11-21 15:13:05]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int vis[101][101][2];
int mark[101][101][2];
#define For(i,a,b) for(int i = a; i <= b; ++i)
int x,y,p,q;
int Dfs(int w,int s,int flag){

    if((flag == 0 && (y - s && x - w > y - s + q)) || (flag == 1 && (s && w > s + q)))
        return 1e9;
    if(vis[w][s][flag] < 300000){
        return vis[w][s][flag];
    } if(flag == 1 && s == 0){
        return vis[w][s][flag] = 0;
    }
    if(mark[w][s][flag]) return 1e9;
    mark[w][s][flag] = 1;
   
    int ans = 1e9;
    int cw = flag == 1 ? x - w : w;
    int cs = flag == 1 ? y - s : s;
    for(int i = 0; i <= min(cw,p); ++ i){
        for(int j = 0; j <= cs && j + i <= p; ++j){
            // if(i + j != p) continue;
            if(cw - i <= cs - j + q || cs - j == 0){
                ans = min(ans,Dfs(w + (flag == 1 ? i : -i),s + (flag == 1 ? j : -j),flag ^ 1) + 1);
            }
        }
    }
    mark[w][s][flag] = 0;    return vis[w][s][flag] = ans;
}
signed main()
{
    #ifdef NICEGUODONG
        freopen("data.in","r",stdin);
    #endif
    ios::sync_with_stdio(false);
    
    cin >> x >> y >> p >> q;
    swap(x,y);
    For(i,0,100) For(j,0,100) vis[i][j][0] = vis[i][j][1] = 1e8;
    int ans = 1e9;
    ans = Dfs(x,y,0);
    if(ans <= 300000)
        cout << ans;
    else
        cout << -1;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

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

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: -100
Time Limit Exceeded

input:

10 9 1 10

output:


result: