Contest link
[Contest][1]
Difficulty: Med-hard
Explanation
We will use binary search to find the answer. Further we will use Ford-Bellman algorithm. On each step we will have an array of maximum values on timer, when we stand in some point. On in transfer we will check: will our player stay alive after travelling beetwen points. If we can make transfer, we will update value of the final destination point. Becouse of a_i<=d and integer coordinates we haven’t optimal cycles, and solution exists.Check the Following code for better understanding
[1]: http://www.codechef.com/CDCR2015/problems/CDCR15_5
int func(int r, int n, int d) {
int s, i, j;
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
priority_queue <pp, vector , Prioritize> q;
q.push(pp(0, r));
dis[0] = 0;
while (!q.empty()) {
s = q.top().first;
r = q.top().second;
r += a[s];
q.pop();
if (vis[s])
continue;
//cout << s << " " << dis[s] << " " << r << endl;
vis[s] = 1;
for (i = 1; i < n; i++) {
if (!vis[i]){
j = (abs(p[i].x - p[s].x) + abs(p[i].y - p[s].y))*d;
//cout <" << j << " " << dis[i] << " " << i <= dis[i])) {
dis[i] = r - j;
q.push(pp(i, dis[i]));
}
}
}
}
if (vis[n - 1])
return 1;
else
return 0;
}
void bsearch()
{
s = 1;
e = INF;
while (s < e) {
mid = (s + e) / 2;
j = func(mid, n, d);
if (j == 1) {
e = mid;
}
else
s = mid + 1;
}
cout << e << endl;
}