Code
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
long double dist(long long x, long long y, long long p, long long q) {
return sqrtl((x - p) * (x - p) + (y - q) * (y - q));
}
void solve(vector<long long> &x, vector<long long> &y, int start_x, int start_y,
int max_k) {
int n = x.size();
// Pushing a dummy value at the end.
x.push_back(-1);
y.push_back(-1);
vector<long double> dist_from_origin(n + 1), dist_from_prev(n + 1),
pref_sum(n + 1), delta(n + 1);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = dist(start_x, start_y, x[i], y[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = dist(x[i], y[i], x[i - 1], y[i - 1]);
pref_sum[i] = pref_sum[i - 1] + dist_from_prev[i];
}
for (int i = 0; i < n; i++) {
delta[i] =
dist_from_origin[i] + dist_from_origin[i + 1] - pref_sum[i + 1];
}
// dp[i] represents the minimum distance travelled to gift the first i
// children.
vector<long double> dp(n, inf);
multiset<long double> mset;
dp[0] = dist_from_origin[0];
mset.insert(dp[0] + delta[0]);
for (int i = 1; i < n; i++) {
// When did you last refill?
//
// Case 1 : You last refilled at j-th index.
dp[i] = *mset.begin() + pref_sum[i];
// Case 2 : No refill needed.
//
// There are i - 0 + 1 persons in the interval [0 ... i].
// If max_k is sufficient for all of them, there would be no refill.
if (max_k >= (i - 0 + 1)) {
dp[i] = min(dp[i], dp[i - 1] + dist_from_prev[i]);
}
mset.insert(dp[i] + delta[i]);
if ((int)mset.size() > max_k) {
// j is the index of the oldest element.
int j = i - max_k;
mset.erase(mset.find(dp[j] + delta[j]));
}
}
cout << dp[n - 1] + dist_from_origin[n - 1] << " ";
cout << endl;
}
int main() {
cout << setprecision(20);
int n, k;
cin >> n >> k;
int start_x, start_y;
cin >> start_x >> start_y;
vector<long long> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
}
solve(x, y, start_x, start_y, k);
return 0;
}These 3 solutions are featured in the Youtube video.
#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
long long query(vector<long long> &pref, int l, int r) {
if (l > r) {
return 0;
}
return pref[r] - (l ? pref[l - 1] : 0);
}
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
// Pushing a dummy value at the end.
a.push_back(-1);
vector<long long> dist_from_origin(n + 1), dist_from_prev(n + 1),
pref_sum(n + 1), delta(n + 1);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
pref_sum[i] = pref_sum[i - 1] + dist_from_prev[i];
}
for (int i = 0; i < n; i++) {
delta[i] =
dist_from_origin[i] + dist_from_origin[i + 1] - pref_sum[i + 1];
}
// dp[i] represents the minimum distance travelled to gift the first i
// children.
vector<long long> dp(n, inf);
multiset<long long> mset;
dp[0] = dist_from_origin[0];
mset.insert(dp[0] + delta[0]);
for (int i = 1; i < n; i++) {
// When did you last refill?
//
// Case 1 : You last refilled at j-th index.
dp[i] = *mset.begin() + pref_sum[i];
// Case 2 : No refill needed.
//
// There are i - 0 + 1 persons in the interval [0 ... i].
// If max_k is sufficient for all of them, there would be no refill.
if (max_k >= (i - 0 + 1)) {
dp[i] = min(dp[i], dp[i - 1] + dist_from_prev[i]);
}
mset.insert(dp[i] + delta[i]);
if ((int)mset.size() > max_k) {
// j is the index of the oldest element.
int j = i - max_k;
mset.erase(mset.find(dp[j] + delta[j]));
}
}
for (int i = 0; i < n; i++) {
cout << dp[i] + dist_from_origin[i] << " ";
}
cout << endl;
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
long long query(vector<long long> &pref, int l, int r) {
if (l > r) {
return 0;
}
return pref[r] - (l ? pref[l - 1] : 0);
}
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
vector<long long> dist_from_origin(n), dist_from_prev(n), pref_sum(n);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
pref_sum[i] = pref_sum[i - 1] + dist_from_prev[i];
}
// dp[i] represents the minimum distance travelled to gift the first i
// children.
vector<long long> dp(n, inf);
dp[0] = dist_from_origin[0];
for (int i = 1; i < n; i++) {
// When did you last refill?
//
// Case 1 : You last refilled at j-th index.
for (int j = i - 1; j >= max(0, i - max_k); j--) {
long long cost = dist_from_origin[j] + dist_from_origin[j + 1];
cost += query(pref_sum, j + 2, i);
dp[i] = min(dp[i], dp[j] + cost);
}
// Case 2 : No refill needed.
// There are i - 0 + 1 persons in the interval [0 ... i].
// If max_k is sufficient for all of them, there would be no refill.
if (max_k >= (i - 0 + 1)) {
dp[i] = min(dp[i], dp[i - 1] + dist_from_prev[i]);
}
}
for (int i = 0; i < n; i++) {
cout << dp[i] + dist_from_origin[i] << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
vector<long long> dist_from_origin(n), dist_from_prev(n);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
}
// dp[i] represents the minimum distance travelled to gift the first i
// children.
vector<long long> dp(n, inf);
dp[0] = dist_from_origin[0];
for (int i = 1; i < n; i++) {
// When did you last refill?
//
// Case 1 : You last refilled at j-th index.
for (int j = i - 1; j >= max(0, i - max_k); j--) {
long long cost = dist_from_origin[j] + dist_from_origin[j + 1];
for (int k = j + 2; k <= i; k++) {
cost += dist_from_prev[k];
}
dp[i] = min(dp[i], dp[j] + cost);
}
// Case 2 : No refill needed.
// There are i - 0 + 1 persons in the interval [0 ... i].
// If max_k is sufficient for all of them, there would be no refill.
if (max_k >= (i - 0 + 1)) {
dp[i] = min(dp[i], dp[i - 1] + dist_from_prev[i]);
}
}
for (int i = 0; i < n; i++) {
cout << dp[i] + dist_from_origin[i] << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
vector<long long> dist_from_origin(n), dist_from_prev(n);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
}
// dp[j] represents the minimum distance travelled to gift
// chidren seen so far, when there are j presents in the box when we
// reach the last child seen so far.
vector<long long> dp(max_k + 2, inf);
for (int j = 1; j <= max_k; j++) {
dp[j] = dist_from_origin[0];
}
cout << *min_element(dp.begin(), dp.end()) + dist_from_origin[0] << " ";
for (int i = 1; i < n; i++) {
long long mn = inf;
for (int j = 1; j <= max_k; j++) {
mn = min(mn, dp[j] + dist_from_origin[i] + dist_from_origin[i - 1]);
dp[j] = min(mn, dp[j + 1] + dist_from_prev[i]);
}
cout << *min_element(dp.begin(), dp.end()) + dist_from_origin[i] << " ";
}
cout << endl;
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
vector<long long> dist_from_origin(n), dist_from_prev(n);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
}
// dp[i][j] represents the minimum distance travelled to gift
// chidren [1 ... i] only, when there are j presents in the box when we
// reach the i-th child.
vector<vector<long long>> dp(n, vector<long long>(max_k + 2, inf));
vector<vector<long long>> prefix_min(n, vector<long long>(max_k + 2, inf));
for (int j = 1; j <= max_k; j++) {
dp[0][j] = dist_from_origin[0];
prefix_min[0][j] = min(prefix_min[0][j - 1], dp[0][j]);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= max_k; j++) {
// If you have j presents when you reach the i-th child, how many
// presents did you have when you reached the (i - 1)th child?
// Case 1 : You had j + 1 presents.
dp[i][j] = dp[i - 1][j + 1] + dist_from_prev[i];
// Case 2 : You had <= j presents. So, you give one to the
// (i - 1)th child, and then you go back to fill the remaining
// presents.
dp[i][j] =
min(dp[i][j], prefix_min[i - 1][j] + dist_from_origin[i] +
dist_from_origin[i - 1]);
}
for (int j = 1; j <= max_k; j++) {
prefix_min[i][j] = min(prefix_min[i][j - 1], dp[i][j]);
}
}
for (int i = 0; i < n; i++) {
long long ans = inf;
for (int j = 1; j <= max_k; j++) {
ans = min(ans, dp[i][j]);
}
ans += dist_from_origin[i];
cout << ans << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e15;
void solve(vector<long long> &a, int start, int max_k) {
int n = a.size();
vector<long long> dist_from_origin(n), dist_from_prev(n);
for (int i = 0; i < n; i++) {
dist_from_origin[i] = abs(start - a[i]);
}
for (int i = 1; i < n; i++) {
dist_from_prev[i] = abs(a[i] - a[i - 1]);
}
// dp[i][j] represents the minimum distance travelled to gift
// chidren [1 ... i] only, when there are j presents in the box when we
// reach the i-th child.
vector<vector<long long>> dp(n, vector<long long>(max_k + 2, inf));
for (int j = 1; j <= max_k; j++) {
dp[0][j] = abs(start - a[0]);
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= max_k; j++) {
// If you have j presents when you reach the i-th child, how many
// presents did you have when you reached the (i - 1)th child?
// Case 1 : You had j + 1 presents.
dp[i][j] = dp[i - 1][j + 1] + dist_from_prev[i];
// Case 2 : You had <= j presents. So, you give one to the
// (i - 1)th child, and then you go back to fill the remaining
// presents.
for (int k = 1; k <= j; k++) {
dp[i][j] = min(dp[i][j], dp[i - 1][k] + dist_from_origin[i] +
dist_from_origin[i - 1]);
}
}
}
for (int i = 0; i < n; i++) {
long long ans = inf;
for (int j = 1; j <= max_k; j++) {
ans = min(ans, dp[i][j]);
}
ans += dist_from_origin[i];
cout << ans << " ";
}
cout << "\n";
}
int main() {
int t;
cin >> t;
for (int zz = 0; zz < t; zz++) {
int n, k;
cin >> n >> k;
int start;
cin >> start;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
solve(a, start, k);
}
return 0;
}