#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn = 110, maxs = 1e4+10;
int n, m, a, b, mat[maxn][maxn], k;
struct pt
{
ll f;
int sf, ss;
bool operator > (const pt &k) const{
if(f != k.f) return f > k.f;
else if(sf != k.sf) return sf > k.sf;
else return ss >= k.ss;
}
}dp[maxn][maxn][2];
pt solve()
{
int mod = 0;
for(int t = 1 ; t <= min(k, 10000) ; t++)
{
mod ^= 1;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
if(i == 3 and j == 3)
{
cout << dp[i-1][j][mod^1].f << ' ' << dp[i][j+1][mod^1].f << ' ' << dp[i][j-1][mod^1].f << ' ' << dp[i+1][j][mod^1].f << endl;
}
if(dp[i-1][j][mod^1] > dp[i+1][j][mod^1] and dp[i-1][j][mod^1] > dp[i][j-1][mod^1] and dp[i-1][j][mod^1] > dp[i][j+1][mod^1])
{
dp[i][j][mod] = dp[i-1][j][mod^1];
if(mat[i][j] > dp[i-1][j][mod^1].sf)
{
dp[i][j][mod].ss = dp[i-1][j][mod^1].sf;
dp[i][j][mod].sf = mat[i][j];
}
else if(mat[i][j] > dp[i-1][j][mod^1].ss) dp[i][j][mod].ss = mat[i][j];
}
else if(dp[i+1][j][mod^1] > dp[i-1][j][mod^1] and dp[i+1][j][mod^1] > dp[i][j-1][mod^1] and dp[i+1][j][mod^1] > dp[i][j+1][mod^1])
{
dp[i][j][mod] = dp[i+1][j][mod^1];
if(mat[i][j] > dp[i+1][j][mod^1].sf)
{
dp[i][j][mod].ss = dp[i+1][j][mod^1].sf;
dp[i][j][mod].sf = mat[i][j];
}
else if(mat[i][j] > dp[i+1][j][mod^1].ss) dp[i][j][mod].ss = mat[i][j];
}
else if(dp[i][j-1][mod^1] > dp[i-1][j][mod^1] and dp[i][j-1][mod^1] > dp[i+1][j][mod^1] and dp[i][j-1][mod^1] > dp[i][j+1][mod^1])
{
dp[i][j][mod] = dp[i][j-1][mod^1];
if(mat[i][j] > dp[i][j-1][mod^1].sf)
{
dp[i][j][mod].ss = dp[i][j-1][mod^1].sf;
dp[i][j][mod].sf = mat[i][j];
}
else if(mat[i][j] > dp[i][j-1][mod^1].ss) dp[i][j][mod].ss = mat[i][j];
}
else
{
dp[i][j][mod] = dp[i][j+1][mod^1];
if(mat[i][j] > dp[i][j+1][mod^1].sf)
{
dp[i][j][mod].ss = dp[i][j+1][mod^1].sf;
dp[i][j][mod].sf = mat[i][j];
}
else if(mat[i][j] > dp[i][j+1][mod^1].ss) dp[i][j][mod].ss = mat[i][j];
}
if(dp[i][j][mod].f != -1) dp[i][j][mod].f += mat[i][j];
if(dp[i][j][mod].sf < dp[i][j][mod].ss) swap(dp[i][j][mod].sf, dp[i][j][mod].ss);
}
}
cout << endl << t << endl;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cout << dp[i][j][mod].f << ' ';
}
cout << endl;
}
//cout << endl;
}
return dp[a][b][mod];
}
int main()
{
cin >> n >> m >> a >> b >> k;
for(int i = 1 ; i <= n ; i++)
{
for(int j = 1 ; j <= m ; j++)
{
cin >> mat[i][j];
}
}
memset(dp, -1, sizeof dp);
dp[a][b][0].f = 0;
pt resp = solve();
if(k < 1e4) cout << resp.f << endl;
else cout << resp.f + (resp.sf+resp.ss)*k/2 << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
46 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
57 ms |
2552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
80 ms |
3576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2013 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
503 ms |
36192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2059 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2036 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
934 ms |
54244 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2065 ms |
65536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
