QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655104#7781. Sheep Eat WolvesenarTL 1245ms3980kbC++201.1kb2024-10-19 00:35:352024-10-19 00:35:36

Judging History

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

  • [2024-10-19 00:35:36]
  • 评测
  • 测评结果:TL
  • 用时:1245ms
  • 内存:3980kb
  • [2024-10-19 00:35:35]
  • 提交

answer

#include <bits/stdc++.h>
using i64 = long long;
const int INF = 1E4;

void solve() {
    int x, y, p, q;
    std::cin >> x >> y >> p >> q;
    std::vector dp(2, std::vector(x + 1, std::vector<int>(y + 1, INF)));
    dp[0][0][0] = dp[1][x][y] = 0;
    int opt = 0;
    for(int t = 0; t <= 200; ++t, opt ^= 1) {
        for(int i = 0; i <= p; ++i) { 
            for(int j = 0; j <= p - i; ++j) { 
                for(int a = i; a <= x; ++a) { 
                    for(int b = j; b <= y; ++b) {
                        if(x - a + q < y - b && x != a) continue;
                        dp[opt][a][b] = std::min(dp[opt][a][b], dp[opt ^ 1][x - a + i][y - b + j] + 1); 
                    }
                }
            }
        }
    }   
    i64 sum = 0; 
    int mn = INF;
    for(int i = 0; i <= y; ++i) {
        mn = std::min(mn, dp[0][x][i]);
    }
    std::cout << (mn == INF ? -1 : mn) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    // std::cin >> T;
    while(T--) {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

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

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

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

input:

15 20 2 5

output:

27

result:

ok 1 number(s): "27"

Test #9:

score: 0
Accepted
time: 23ms
memory: 3568kb

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

score: 0
Accepted
time: 48ms
memory: 3864kb

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

score: 0
Accepted
time: 50ms
memory: 3640kb

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

score: 0
Accepted
time: 51ms
memory: 3556kb

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

score: 0
Accepted
time: 150ms
memory: 3828kb

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 157ms
memory: 3612kb

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: 0
Accepted
time: 160ms
memory: 3672kb

input:

60 60 16 16

output:

11

result:

ok 1 number(s): "11"

Test #16:

score: 0
Accepted
time: 167ms
memory: 3560kb

input:

60 60 16 24

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

75 15 1 1

output:

175

result:

ok 1 number(s): "175"

Test #18:

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

input:

50 100 1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 197ms
memory: 3752kb

input:

100 100 10 10

output:

35

result:

ok 1 number(s): "35"

Test #20:

score: 0
Accepted
time: 185ms
memory: 3904kb

input:

100 100 10 1

output:

37

result:

ok 1 number(s): "37"

Test #21:

score: 0
Accepted
time: 207ms
memory: 3980kb

input:

100 100 10 20

output:

33

result:

ok 1 number(s): "33"

Test #22:

score: 0
Accepted
time: 216ms
memory: 3900kb

input:

100 100 10 30

output:

31

result:

ok 1 number(s): "31"

Test #23:

score: 0
Accepted
time: 232ms
memory: 3952kb

input:

100 100 10 80

output:

21

result:

ok 1 number(s): "21"

Test #24:

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

input:

100 100 1 100

output:

199

result:

ok 1 number(s): "199"

Test #25:

score: 0
Accepted
time: 63ms
memory: 3784kb

input:

100 100 5 0

output:

95

result:

ok 1 number(s): "95"

Test #26:

score: 0
Accepted
time: 914ms
memory: 3728kb

input:

100 100 25 3

output:

13

result:

ok 1 number(s): "13"

Test #27:

score: 0
Accepted
time: 1245ms
memory: 3688kb

input:

100 100 30 4

output:

11

result:

ok 1 number(s): "11"

Test #28:

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

input:

95 100 3 3

output:

125

result:

ok 1 number(s): "125"

Test #29:

score: -100
Time Limit Exceeded

input:

98 99 50 6

output:


result: