Code : Earn to Advance
This solution is technically correct, but TLEs due to the extra log factor in map. However, you can use it as a starting point while implementing the editorial’s solution.
- Of course, you can remove the log factor by keeping a 4D DP matrix, but it’s not necessary as long as you understand how to theoretically optimize it, and have gotten AC on at least 21 testcases.
- There is code duplication for the right vs down part. You can reduce the code using fancy lambda, but then again, it’s not strictly necessary as long as you understand what you’re doing while copy-pasting the code.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
typedef pair<long long, long long> pll;
// See editorial on CF Step to understand what these DP states and transitions
// represent.
void solve(vector<vector<int>> &p, vector<vector<int>> &r,
vector<vector<int>> &d) {
int n = p.size();
map<int, vector<vector<pll>>> mdp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mdp[p[i][j]] = vector<vector<pll>>(n, vector<pll>(n, {inf, 0}));
}
}
mdp[p[0][0]][0][0] = {0, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (auto &[max_p, dp] : mdp) {
if (j + 1 < n) {
auto actions = dp[i][j].first;
auto left_over_money = dp[i][j].second;
actions++;
auto need = max(0LL, r[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= r[i][j];
auto &nxt = mdp[max(max_p, p[i][j + 1])][i][j + 1];
if (nxt.first > actions || (nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
// Exactly same as above code, with (i, j + 1) replaced with
// (i + 1, j).
if (i + 1 < n) {
auto actions = dp[i][j].first;
auto left_over_money = dp[i][j].second;
actions++;
auto need = max(0LL, d[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= d[i][j];
auto &nxt = mdp[max(max_p, p[i + 1][j])][i + 1][j];
if (nxt.first > actions || (nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
}
}
}
long long ans = inf;
for (auto &[max_p, dp] : mdp) {
ans = min(ans, dp[n - 1][n - 1].first);
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> p[i][j];
}
}
vector<vector<int>> r(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
cin >> r[i][j];
}
}
vector<vector<int>> d(n, vector<int>(n, 0));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
cin >> d[i][j];
}
}
solve(p, r, d);
return 0;
}Same solution as before, but uses unordered map to verify that the logic was correct. It ACs, but is close to the time limit.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
typedef pair<long long, long long> pll;
// See editorial on CF Step to understand what these DP states and transitions
// represent.
void solve(vector<vector<int>> &p, vector<vector<int>> &r,
vector<vector<int>> &d) {
int n = p.size();
unordered_map<int, vector<vector<pll>>> mdp;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mdp[p[i][j]] = vector<vector<pll>>(n, vector<pll>(n, {inf, 0}));
}
}
mdp[p[0][0]][0][0] = {0, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (auto &[max_p, dp] : mdp) {
if (j + 1 < n) {
auto actions = dp[i][j].first;
auto left_over_money = dp[i][j].second;
actions++;
auto need = max(0LL, r[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= r[i][j];
auto &nxt = mdp[max(max_p, p[i][j + 1])][i][j + 1];
if (nxt.first > actions || (nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
// Exactly same as above code, with (i, j + 1) replaced with
// (i + 1, j).
if (i + 1 < n) {
auto actions = dp[i][j].first;
auto left_over_money = dp[i][j].second;
actions++;
auto need = max(0LL, d[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= d[i][j];
auto &nxt = mdp[max(max_p, p[i + 1][j])][i + 1][j];
if (nxt.first > actions || (nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
}
}
}
long long ans = inf;
for (auto &[max_p, dp] : mdp) {
ans = min(ans, dp[n - 1][n - 1].first);
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> p[i][j];
}
}
vector<vector<int>> r(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
cin >> r[i][j];
}
}
vector<vector<int>> d(n, vector<int>(n, 0));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
cin >> d[i][j];
}
}
solve(p, r, d);
return 0;
}Same solution as before, but uses 4D DP instead of map. Feel free to skip it if implementation heavy problems are not your cup of tea.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
typedef pair<long long, long long> pll;
// See editorial on CF Step to understand what these DP states and transitions
// represent.
void solve(vector<vector<int>> &p, vector<vector<int>> &r,
vector<vector<int>> &d) {
int n = p.size();
// dp[i][j][x][y] means the max p value is present at cell (x, y).
vector<vector<vector<vector<pll>>>> dp(
n, vector<vector<vector<pll>>>(
n, vector<vector<pll>>(n, vector<pll>(n, {inf, 0}))));
dp[0][0][0][0] = {0, 0};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (j + 1 < n) {
auto max_p = p[x][y];
auto actions = dp[i][j][x][y].first;
auto left_over_money = dp[i][j][x][y].second;
actions++;
auto need = max(0LL, r[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= r[i][j];
int nx, ny;
if (p[x][y] > p[i][j + 1]) {
nx = x, ny = y;
} else {
nx = i, ny = j + 1;
}
auto &nxt = dp[i][j + 1][nx][ny];
if (nxt.first > actions ||
(nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
// Exactly same as above code, with (i, j + 1) replaced with
// (i + 1, j).
if (i + 1 < n) {
auto max_p = p[x][y];
auto actions = dp[i][j][x][y].first;
auto left_over_money = dp[i][j][x][y].second;
actions++;
auto need = max(0LL, d[i][j] - left_over_money);
auto op = need / max_p + (need % max_p != 0);
actions += op;
left_over_money += op * max_p;
left_over_money -= d[i][j];
int nx, ny;
if (p[x][y] > p[i + 1][j]) {
nx = x, ny = y;
} else {
nx = i + 1, ny = j;
}
auto &nxt = dp[i + 1][j][nx][ny];
if (nxt.first > actions ||
(nxt.first == actions &&
nxt.second < left_over_money)) {
nxt = {actions, left_over_money};
}
}
}
}
}
}
long long ans = inf;
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
ans = min(ans, dp[n - 1][n - 1][x][y].first);
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<vector<int>> p(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> p[i][j];
}
}
vector<vector<int>> r(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
cin >> r[i][j];
}
}
vector<vector<int>> d(n, vector<int>(n, 0));
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
cin >> d[i][j];
}
}
solve(p, r, d);
return 0;
}