QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#648128 | #7781. Sheep Eat Wolves | enar# | TL | 900ms | 105064kb | C++20 | 1.6kb | 2024-10-17 17:10:46 | 2024-10-17 17:10:46 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
const int INF = 1E9;
struct Node {
int cnt, sp, wv;
bool operator < (const Node &u) const {
return cnt > u.cnt;
}
};
void solve() {
int x, y, p, q;
std::cin >> x >> y >> p >> q;
std::priority_queue<Node> pq;
std::vector vis(2, std::vector(400, std::vector<int>(400)));
int ans = INF;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto [c, a, b] = pq.top();
pq.pop();
vis[c % 2][a][b] = 1;
if (a == x) {
ans = std::min(ans, c);
break;
}
if (c % 2 == 0) {
for (int i = 0; i <= x - a && i <= p; ++i) {
for (int j = 0; j <= y - b && j <= p - i; ++j) {
if (y - b - j > x - a - i + q && a + i != x) continue;
if (vis[(c + 1) % 2][a + i][b + j]) continue;
pq.push({c + 1, a + i, b + j});
}
}
} else {
for (int i = 0; i <= a && i <= p; ++i) {
for (int j = 0; j <= b && j <= p - i; ++j) {
if (b - j > a - i + q && a - i != 0) continue;
if (vis[(c + 1) % 2][a - i][b - j]) continue;
pq.push({c + 1, a - i, b - j});
}
}
}
}
if (ans == INF) ans = -1;
std::cout << ans << "\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: 0ms
memory: 5396kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5316kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5328kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5320kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4956kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4912kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4916kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 900ms
memory: 105064kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 6ms
memory: 12804kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: -100
Time Limit Exceeded
input:
60 60 8 1