# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
118718 |
2019-06-19T14:07:56 Z |
sofhiasouza |
Maja (COCI18_maja) |
C++14 |
|
948 ms |
888 KB |
#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;
bool operator > (const pt &k) const{
if(f != k.f) return f > k.f;
return sf > k.sf;
}
}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(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]+mat[i-1][j] > dp[i-1][j][mod^1].sf) dp[i][j][mod].sf = mat[i][j]+mat[i-1][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]+mat[i+1][j] > dp[i+1][j][mod^1].sf) dp[i][j][mod].sf = mat[i][j]+mat[i+1][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]+mat[i][j-1] > dp[i][j-1][mod^1].sf) dp[i][j][mod].sf = mat[i][j]+mat[i][j-1];
}
else
{
dp[i][j][mod] = dp[i][j+1][mod^1];
if(mat[i][j]+mat[i][j+1] > dp[i][j+1][mod^1].sf) dp[i][j][mod].sf = mat[i][j]+mat[i][j+1];
}
if(dp[i][j][mod].f != -1) dp[i][j][mod].f += mat[i][j];
}
}
}
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 < 10000) cout << resp.f << endl;
else cout << (unsigned long long int)resp.f + (unsigned long long int)(resp.sf)*((unsigned long long int)k-10000)/2 << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
640 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
768 KB |
Output is correct |
2 |
Correct |
10 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
768 KB |
Output is correct |
2 |
Correct |
18 ms |
640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
640 KB |
Output is correct |
2 |
Correct |
5 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
308 ms |
760 KB |
Output is correct |
2 |
Correct |
22 ms |
768 KB |
Output is correct |
3 |
Correct |
948 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
736 KB |
Output is correct |
2 |
Correct |
501 ms |
772 KB |
Output is correct |
3 |
Correct |
588 ms |
780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
649 ms |
780 KB |
Output is correct |
2 |
Correct |
766 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
258 ms |
768 KB |
Output is correct |
2 |
Correct |
227 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
860 KB |
Output is correct |
2 |
Correct |
28 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
772 KB |
Output is correct |
2 |
Incorrect |
22 ms |
780 KB |
Output isn't correct |