QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #724450 | #7781. Sheep Eat Wolves | juan_123# | TL | 32ms | 4964kb | C++14 | 1.1kb | 2024-11-08 13:12:20 | 2024-11-08 13:12:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
const int inf = 1000000000;
int dis[2][105][105];
int X,Y,p,q;
bool check(int x,int y){
if(x==0)return 1;
return y-x<=q;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> X >> Y >> p >> q;
queue<pair<int,pair<int,int> > >q;
for(int i =0;i<=X;i++)for(int j =0;j<=Y;j++)dis[0][i][j]=dis[1][i][j]=inf;
q.push({0,{X,Y}});dis[0][X][Y]=0;
while(!q.empty()){
int tp = q.front().first,x = q.front().second.first,y = q.front().second.second;
// cout <<" " << tp << " " << x << " " << y << " " << dis[tp][x][y] <<endl;
q.pop();
for(int i =0;i<=x;i++){
for(int j =0;j<=y;j++){
if(i+j>p or !check(x-i,y-j))continue;
int xx = X-(x-i),yy = Y-(y-j);
// cout << x-i << " " << y-j << " " << xx << " " << yy << endl;
if(dis[tp^1][xx][yy]>dis[tp][x][y]){
dis[tp^1][xx][yy] = dis[tp][x][y]+1;
q.push({tp^1,{xx,yy}});
}
}
}
}
int ans = inf;
for(int i = 0;i<=Y;i++)ans = min(ans,dis[1][X][i]);
if(ans == inf)ans = -1;
cout << ans << endl;
return 0;
}/*
4 4 3 1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3832kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 32ms
memory: 4964kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: -100
Time Limit Exceeded
input:
15 20 2 5