This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
const int MAXN=110;
int n,m,a,b,k;
int P[MAXN][MAXN];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
ll dp[MAXN][MAXN][2];
bool valid(int x,int y){
if(x<0||x>=n) return false;
if(y<0||y>=m) return false;
return true;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>m>>a>>b>>k;
a--;b--;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>P[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dp[i][j][0]=-1;
dp[i][j][1]=-1;
}
}
dp[a][b][0]++;
while(k--){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(dp[i][j][0]!=-1){
int x,y;
for(int d=0;d<4;d++){
x=i+dx[d];
y=j+dy[d];
if(valid(x,y)){
dp[x][y][1]=max(dp[x][y][1],dp[i][j][0]+P[x][y]);
}
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
dp[i][j][0]=dp[i][j][1];
dp[i][j][1]=-1;
}
}
}
cout<<dp[a][b][0]<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |