DELOITTE EXAM SOLUTIONS: post #16250 — TG.ME

int solve(int N, int P, vector<vector<int>>& costs) { int half = N / 2; const int MAX_VAL = 1e9; vector<vector<vector<int>>> table(N + 1, vector<vector<int>>(half + 1, vector<int>(2, MAX_VAL))); table[1][1][0] = costs[0][0]; table[1][0][1] = costs[0][1]; for (int idx = 1; idx < N; idx++) { for (int cityA_cnt = 0; cityA_cnt <= half; cityA_cnt++) { for (int prev_city = 0; prev_city < 2; prev_city++) { if (table[idx][cityA_cnt][prev_city] == MAX_VAL) continue; if (cityA_cnt + 1 <= half) { int extra = (prev_city == 0) ? P : 0; table[idx + 1][cityA_cnt + 1][0] = min(table[idx + 1][cityA_cnt + 1][0], table[idx][cityA_cnt][prev_city] + costs[idx][0] + extra); } int cityB_cnt = idx - cityA_cnt; if (cityB_cnt + 1 <= half) { int extra = (prev_city == 1) ? P : 0; table[idx + 1][cityA_cnt][1] = min(table[idx + 1][cityA_cnt][1], table[idx][cityA_cnt][prev_city] + costs[idx][1] + extra); } } } } return min(table[N][half][0], table[N][half][1]);