oj.uz

Submission #461305

# Submission time Handle Problem Language Result Execution time Memory
461305 2021-08-09T17:21:30 Z grt Maja (COCI18_maja) C++17
44 / 110
 728 ms 652 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 15 ms 332 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 16 ms 360 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 7 ms 332 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

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

Subtask #9
0 / 11.0

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

Subtask #10
0 / 11.0

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