Submission #461305

#	Time	Username	Problem	Language	Result	Execution time	Memory
461305		grt	Maja (COCI18_maja)	C++17	44 / 110	728 ms	652 KiB

maja

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 110;
const ll INF = 1e18;
int n, m, k, a, b;
int c[nax][nax];
ll dp[nax][nax][2];
ll dp2[nax][nax][2];

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

int main() {_
	cin >> n >> m >> a >> b >> k;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> c[i][j];
			if(i == a && j == b) {
				dp[a][b][0] = 0;
			} else {
				dp[i][j][0] = -INF;
			}
		}
	}
	for(int s = 1; s <= min(10000, k); ++s) {
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= m; ++j) {
				dp[i][j][s&1] = -INF;
				for(int d = 0; d < 4; ++d) {
					if(i + dx[d] > 0 && i + dx[d] <= n && j + dy[d] > 0 && j + dy[d] <= m) {
						dp[i][j][s&1] = max(dp[i][j][s&1],dp[i + dx[d]][j + dy[d]][1 - (s&1)] + c[i][j]);
					}
				}
				if(dp[i][j][s&1] < 0) dp[i][j][s&1] = -INF;
			}
		}
		if(s == 4999) {
			for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dp2[i][j][1] = dp[i][j][1];
		} else if(s == 5000) {
			for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) dp2[i][j][0] = dp[i][j][0];
		}
	}
	if(k <= 10000) {
		cout << dp[a][b][0];
	} else {
		ll ans = -INF;
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= m; ++j) {
				for(int d = 0; d < 4; ++d) {
					if(i + dx[d] > 0 && i + dx[d] <= n && j + dy[d] > 0 && j + dy[d] <= m) {
						if((a + b) % 2 == (i + j) % 2) {
							ans = max(ans, dp2[i][j][0] + dp2[i + dx[d]][j + dy[d]][1]) + 1LL * ((k - 10000) / 2) * (c[i][j] + c[i + dx[d]][j + dy[d]]);
						}
					}
				}
			}
		}
		cout << ans;
	}
	
}
 

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 0 / 11
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 11
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11