oj.uz

Submission #127459

# Submission time Handle Problem Language Result Execution time Memory
127459 2019-07-09T11:51:52 Z Vlatko Maja (COCI18_maja) C++14
55 / 110
 7 ms 1528 KB 
#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;
			if (rem % 2 == 0) {
				// 'dance' ends at u
				if (rem - dist[u] < 0) continue;
				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 - dist[v] < 0) continue;
				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.0 / 11.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 2 ms 760 KB Output is correct

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1016 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Incorrect 7 ms 1528 KB Output isn't correct

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Incorrect 3 ms 888 KB Output isn't correct

Subtask #9
11.0 / 11.0

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

Subtask #10
0 / 11.0

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