QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #682729 | #7781. Sheep Eat Wolves | zyq_313# | WA | 1ms | 3948kb | C++14 | 2.2kb | 2024-10-27 17:06:35 | 2024-10-27 17:06:36 |
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;
}
}
}
}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;
}
}
}
}
cout << "-1\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3948kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3640kb
input:
3 3 1 1
output:
-1
result:
wrong answer 1st numbers differ - expected: '7', found: '-1'