QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #682739 | #7781. Sheep Eat Wolves | zyq_313# | WA | 0ms | 3984kb | C++14 | 2.3kb | 2024-10-27 17:10:20 | 2024-10-27 17:10:21 |
Judging History
answer
#include <bits/stdc++.h>
#define i32 int
#define i64 long long
#define pll pair<i64, i64>
const int N = 110;
using namespace std;
i64 dp[2][N][N];//
int x, y, p, q;
int main(){
memset(dp, 0x3f, sizeof dp);
cin >> x >> y >> p >> q;
dp[0][x][y] = 0;
queue<array<int, 3>> qq;
qq.push({0, x, y});
i64 ans = 1e15;
while (!qq.empty()){
auto [o, xx, yy] = qq.front(); qq.pop();
// cout << o << ' ' << xx << ' ' << yy << "------------" << endl;
if (o == 0){
for (int i = 0; i <= xx; i ++){
for (int j = 0; j <= yy; j ++){
// cout << i << ' ' << i + j << ' ' << yy - j + q << ' ' << xx - i << ' ' << dp[1][xx - i][yy - j] << endl;
// if (xx == 3 && yy == 4 && i == 3 && j == 0) cout << i << ' ' << j << "djwodwo" << endl;
if (i + j > p) continue;
if (yy - j + q > (xx - i) && (xx - i) != 0) continue;
if (dp[1][xx - i][yy - j] != 0x3f3f3f3f3f3f3f3f) continue;
// cout << 1 << ' ' << xx - i << ' ' << yy - j << endl;
qq.push({1, (xx - i), (yy - j)});
dp[1][xx - i][yy - j] = dp[0][xx][yy] + 1;
if (xx - i == 0) {
// cout << dp[1][xx - i][yy - j] << endl;
// return 0;
ans = min(ans, dp[1][xx - i][yy - j]);
}
}
}
}else{
for (int i = 0; i <= x-xx; i ++){
for (int j = 0; j <= y-yy; j ++){
if (i + j > p) continue;
if (y - yy - j + q > (x - xx - i) && (x - xx - i) != 0) continue;
// if (j == 0) cout << "FUCK YOU !!!\n";
if (dp[0][xx + i][yy + j] != 0x3f3f3f3f3f3f3f3f) continue;
// cout << 0 << ' ' << xx + i << ' ' << yy + j << endl;
qq.push({0, xx + i, (yy + j)});
dp[0][xx + i][yy + j] = dp[1][xx][yy] + 1;
// cout << "dhwidwhi" << dp[0][xx + i][yy + j] << ' ' << xx + i << ' ' << yy + j << endl;
}
}
}
}
if (ans != 1e15) cout << ans << endl;
else cout << "-1\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3784kb
input:
3 3 1 1
output:
-1
result:
wrong answer 1st numbers differ - expected: '7', found: '-1'