oj.uz

Submission #118703

# Submission time Handle Problem Language Result Execution time Memory
118703 2019-06-19T12:33:53 Z sofhiasouza Maja (COCI18_maja) C++14
0 / 110
 2000 ms 65536 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, 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;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 2552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 3576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2013 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 503 ms 36192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 934 ms 54244 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -