QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#672094 | #7781. Sheep Eat Wolves | KOH-# | WA | 0ms | 3768kb | C++14 | 1.3kb | 2024-10-24 15:36:02 | 2024-10-24 15:36:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;return;
}
template <typename T>
inline void print(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10^48);return;
}
#define ll long long
const int N=103;
int f[2][N][N];
int x,y,p,q;
void Dfs(int now,int cx,int cy){
// cout<<now<<" "<<cx<<" "<<cy<<" "<<f[now][cx][cy]<<"???\n";
if(now==0){
int tx=x-cx,ty=y-cy;
for(int i=0;i<=p&&i<=cx;++i){
for(int j=0;i+j<=p&&j<=cy;++j){
if(cx-i-(cy-j)<=p){
if(f[0][cx][cy]+1<f[1][cx-i][cy-j]){
f[1][cx-i][cy-j]=f[0][cx][cy]+1;
Dfs(1,cx-i,cy-j);
}
}
}
}
}
else{
int tx=x-cx,ty=y-cy;
for(int i=0;i<=p&&i<=tx;++i){
for(int j=0;i+j<=p&&j<=ty;++j){
if(tx-i-(ty-j)<=p){
if(f[1][cx][cy]+1<f[0][cx+i][cy+j]){
f[0][cx+i][cy+j]=f[1][cx][cy]+1;
Dfs(0,cx+i,cy+j);
}
}
}
}
}
}
int main(){
read(y),read(x),read(p),read(q);
memset(f,0x3f3f3f3f,sizeof(f));
f[0][x][y]=0;
Dfs(0,x,y);
int minn=0x3f3f3f3f;
for(int i=0;i<=x;++i) minn=min(minn,f[1][i][0]);
if(minn!=0x3f3f3f3f) print(minn);
else puts("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3684kb
input:
3 3 1 1
output:
9
result:
wrong answer 1st numbers differ - expected: '7', found: '9'