QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698280#7781. Sheep Eat WolvesQFshengxiuWA 13ms8760kbC++231.8kb2024-11-01 18:35:092024-11-01 18:35:11

Judging History

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

  • [2024-11-01 18:35:11]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:8760kb
  • [2024-11-01 18:35:09]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
using LD = long double;
using PII = pair<int, int>;
const int N = 1e3 + 10;
const int inf = 1e18;
const double eps = 1e-10;
const int mod = 1e9 + 7;
int n, _, m, k, z, p, qx, ans;
bool vis[N][N];
int dis[N][N][2];
bool check(int x, int y, int num)
{
    if (x < 0 || y < 0 || x > n || y > m || dis[x][y][z] != inf)
        return false;
    int lx = n - x, ly = m - num - y;
    return (lx == 0 || lx + qx >= ly);
}
void bfs()
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dis[i][j][0] = dis[i][j][1] = inf;
        }
    }
    queue<array<int, 4>> q;
    q.push({0, 0, 0, 0});
    while (!q.empty())
    {
        auto [x, y, z, w] = q.front();

        q.pop();
        if (dis[x][y][z] <= w)
            continue;
        // cout << x << " " << y << " " << z << ' ' << w << endl;
        dis[x][y][z] = w;
        for (int i = 0; i <= p; i++)
        {
            for (int j = 0; j <= p - i; j++)
            {
                int nx = x + i * (z == 0 ? 1 : -1), ny = y + j * (z == 0 ? 1 : -1), num = p - i - j;
                if (!check(nx, ny, num))
                    continue;
                q.push({nx, ny, 1 - z, w + 1});
            }
        }
    }
    int minn = inf;
    for (int i = 0; i <= m; i++)
    {
        minn = min(minn, dis[n][i][0]);
    }
    if (minn == inf)
        cout << -1 << endl;
    else
        cout << minn - 1 << endl;
}
void solve()
{
    cin >> n >> m >> p >> qx;
    bfs();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

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

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

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

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

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

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

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

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

10 9 1 10

output:

19

result:

ok 1 number(s): "19"

Test #8:

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

input:

15 20 2 5

output:

27

result:

ok 1 number(s): "27"

Test #9:

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

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

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

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

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

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

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

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

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

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

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

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: 0
Accepted
time: 9ms
memory: 6312kb

input:

60 60 16 16

output:

11

result:

ok 1 number(s): "11"

Test #16:

score: 0
Accepted
time: 10ms
memory: 8760kb

input:

60 60 16 24

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

75 15 1 1

output:

175

result:

ok 1 number(s): "175"

Test #18:

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

input:

50 100 1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 9ms
memory: 5344kb

input:

100 100 10 10

output:

35

result:

ok 1 number(s): "35"

Test #20:

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

input:

100 100 10 1

output:

37

result:

ok 1 number(s): "37"

Test #21:

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

input:

100 100 10 20

output:

33

result:

ok 1 number(s): "33"

Test #22:

score: 0
Accepted
time: 7ms
memory: 7512kb

input:

100 100 10 30

output:

31

result:

ok 1 number(s): "31"

Test #23:

score: 0
Accepted
time: 13ms
memory: 7824kb

input:

100 100 10 80

output:

21

result:

ok 1 number(s): "21"

Test #24:

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

input:

100 100 1 100

output:

199

result:

ok 1 number(s): "199"

Test #25:

score: -100
Wrong Answer
time: 3ms
memory: 4608kb

input:

100 100 5 0

output:

77

result:

wrong answer 1st numbers differ - expected: '95', found: '77'