oj.uz

답안 #602084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
602084 2022-07-22T14:40:32 Z Soul234 Maja (COCI18_maja) C++14
99 / 110
 907 ms 844 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int maxn = 110, maxs = 1e4+10;

ll n, m, a, b, mat[maxn][maxn], k;

struct pt
{
	ll f;
	ll 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, (ll)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();
	//cout << resp.f << endl;
	if(k <= 10000) cout << resp.f << endl;
	else cout << (ll)resp.f + (ll)(resp.sf)*((ll)k-10000)/2 << endl;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 10 ms 596 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 14 ms 696 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 5 ms 596 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 684 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 907 ms 760 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 672 KB Output is correct
2 Correct 465 ms 732 KB Output is correct
3 Correct 628 ms 844 KB Output is correct

Subtask #7
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 748 KB Output is correct
2 Correct 687 ms 744 KB Output is correct

Subtask #8
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 214 ms 696 KB Output is correct
2 Correct 180 ms 724 KB Output is correct

Subtask #9
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 680 KB Output is correct
2 Correct 35 ms 596 KB Output is correct

Subtask #10
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 724 KB Output is correct
2 Incorrect 27 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -