Submission #127477

#	Time	Username	Problem	Language	Result	Execution time	Memory
127477		Vlatko	Maja (COCI18_maja)	C++14	55 / 110	6 ms	1400 KiB

maja

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int maxn = 10050;

int N, S;
vector<int> adj[maxn];
ll K;
ll val[maxn];

vector<int> atdist[maxn];
ll dist[maxn];
ll maxdist[maxn];

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	// make graph
	int R, C, A, B;
	cin >> R >> C >> A >> B >> K;
	N = R*C;
	S = (A-1)*C + (B-1);
	for (int u = 0; u < N; ++u) {
		cin >> val[u];
	}
	vector<int> du = {-1, 1, -C, +C};
	for (int u = 0; u < N; ++u) {
		for (int d : du) {
			int v = u + d;
			if (v >= 0 && v < N && (u%C != C-1 || v != u+1) && (u%C != 0 || v != u-1)) {
				adj[u].push_back(v);
			}
		}
	}
	// get distances
	fill(dist, dist+N, -1);
	queue<int> q;
	q.push(S);
	dist[S] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		atdist[dist[u]].push_back(u);
		for (int v : adj[u]) {
			if (dist[v] == -1) {
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	maxdist[S] = 0;
	for (int d = 1; d < N; ++d) {
		for (int u : atdist[d]) {
			maxdist[u] = -1;
			for (int v : adj[u]) {
				if (dist[v] < dist[u]) { // 1 step closer to S
					maxdist[u] = max(maxdist[u], val[u] + maxdist[v]);
				}
			}
		}
	}
	// find best
	ll ans = 0;
	for (int u = 0; u < N; ++u) {
		if (2*dist[u]-1 > K) {
			continue;
		}
		if (2*dist[u]-1 == K) {
			ans = max(ans, maxdist[u] - val[u] + maxdist[u]);
			continue;
		}
		ll rem = K - dist[u];
		if (dist[u] % 2 != rem % 2) {
			continue;
		}
		for (int v : adj[u]) {
			ll dance, res = -1;
			if (rem % 2 == 0) {
				// 'dance' ends at u
				if (rem - dist[u] >= 2) {
					dance = (rem - dist[u]) / 2; // how many times u will be entered
					res = maxdist[u] + val[u]*dance + val[v]*dance - val[u] + maxdist[u];
				}
			} else {
				// 'dance' ends at v
				if (rem - 1 - dist[v] >= 0) {
					dance = (rem - dist[v]) / 2; // how many times u will be entered
					res = maxdist[u] + val[u]*dance + val[v]*(dance+1) - val[v] + maxdist[v];
				}
			}
			if (res > ans) {
				ans = res;
				// cout << "New ans: " << ans << endl;
				// cout << "u=" << u << " v=" << v << endl;
			}
		}
	}
	cout << ans << '\n';
}

• 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: 11 / 11
• Subtask 10: 0 / 11