QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #672231 | #7781. Sheep Eat Wolves | njupt_zy | WA | 12ms | 4796kb | C++17 | 2.1kb | 2024-10-24 16:05:03 | 2024-10-24 16:05:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int bfss[110][110][2];
int n,m,p,q;
template<typename T>
void read(T &x)
{
x=0;
char c=getchar();
bool fla=0;
while(c<'0'||c>'9')
{
if(c=='-')fla=1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+c-'0';
c=getchar();
}
}
typedef struct e{
int x,y,k,cos;
e(int xx,int yy,int kk,int coss)
{
x=xx;
y=yy;
k=kk;
cos=coss;
}
}ee;
void init()
{
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
bfss[i][j][0]=1e9;
bfss[i][j][1]=1e9;
}
}
//bfss[n][m][0]=0;
//bfss[n][m][1]=1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
read(n);
read(m);
read(p);
read(q);
init();
queue<ee>s;
s.push(ee(n,m,0,0));
while(!s.empty())
{
ee cur=s.front();
//cout<<"!"<<cur.x<<" "<<cur.y<<" "<<cur.k<<" "<<cur.cos<<endl;
s.pop();
if(bfss[cur.x][cur.y][cur.k]<=cur.cos)
{
continue;
}
bfss[cur.x][cur.y][cur.k]=cur.cos;
if(cur.k==0)
{
for(int i=0;i<=cur.x;i++)
{
for(int j=0;j<=cur.y;j++)
{
if(i+j>p)continue;
if(cur.x-i!=0&&cur.x-i+q<cur.y-j)continue;
s.push(ee(cur.x-i,cur.y-j,1,cur.cos+1));
}
}
}
else
{
for(int i=0;i<=n-cur.x;i++)
{
for(int j=0;j<=m-cur.y;j++)
{
if(i+j>p)continue;
if(n-cur.x-i!=0&&n-cur.x-i+q<n-cur.y-j)continue;
s.push(ee(cur.x+i,cur.y+j,0,cur.cos+1));
}
}
}
}
int ans=1e9;
for(int i=0;i<=m;i++)
{
ans=min(ans,bfss[0][i][1]);
}
if(ans>=1e9)cout<<-1<<'\n';
else cout<<ans<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3788kb
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: 0ms
memory: 3764kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 1ms
memory: 4036kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
60 60 8 1
output:
27
result:
ok 1 number(s): "27"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
60 60 8 4
output:
27
result:
ok 1 number(s): "27"
Test #12:
score: 0
Accepted
time: 4ms
memory: 3676kb
input:
60 60 8 8
output:
25
result:
ok 1 number(s): "25"
Test #13:
score: 0
Accepted
time: 4ms
memory: 3868kb
input:
60 60 16 1
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 8ms
memory: 4004kb
input:
60 60 16 8
output:
11
result:
ok 1 number(s): "11"
Test #15:
score: 0
Accepted
time: 10ms
memory: 4232kb
input:
60 60 16 16
output:
11
result:
ok 1 number(s): "11"
Test #16:
score: 0
Accepted
time: 12ms
memory: 4796kb
input:
60 60 16 24
output:
9
result:
ok 1 number(s): "9"
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3668kb
input:
75 15 1 1
output:
-1
result:
wrong answer 1st numbers differ - expected: '175', found: '-1'