# Minimum Cost Paths USACO 2021 January Contest

Page Contents

## Minimum Cost Paths USACO Solution

Farmer John’s pasture can be regarded as an N×MN×M (2≤N≤1092≤N≤109, 2≤M≤2⋅1052≤M≤2⋅105) 2D grid of square “cells” (picture a huge chessboard). The cell at the xx-th row from the top and yy-th column from the right is denoted by (x,y)(x,y) for each x∈[1,N],y∈[1,M]x∈[1,N],y∈[1,M]. Furthermore, for each y∈[1,M]y∈[1,M], the yy-th column is associated with the cost cycy (1≤cy≤1091≤cy≤109).

Bessie starts at the cell (1,1)(1,1). If she is currently located at the cell (x,y)(x,y), then she may perform one of the following actions:

• If y<My<M, Bessie may move to the next column (increasing yy by one) for a cost of x2x2.
• If x<Nx<N, Bessie may move to the next row (increasing xx by one) for a cost of cycy.

Given QQ (1≤Q≤2⋅1051≤Q≤2⋅105) independent queries each of the form (xi,yi)(xi,yi) (xi∈[1,N],yi∈[1,M]xi∈[1,N],yi∈[1,M]), compute the minimum possible total cost for Bessie to move from (1,1)(1,1) to (xi,yi)(xi,yi).

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN and MM.

The second line contains MM space-separated integers c1,c2,…,cMc1,c2,…,cM.

The third line contains QQ.

The last QQ lines each contain two space-separated integers xixi and yiyi.

#### OUTPUT FORMAT (print output to the terminal / stdout):

QQ lines, containing the answers for each query.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a “long long” in C/C++).

```5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4
```

#### SAMPLE OUTPUT:

```0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69
```

The output in grid format:

```    1  2  3  4
*--*--*--*--*
1 | 0| 1| 2| 3|
*--*--*--*--*
2 | 1| 5| 9|13|
*--*--*--*--*
3 | 2|11|20|29|
*--*--*--*--*
4 | 3|19|35|49|
*--*--*--*--*
5 | 4|29|54|69|
*--*--*--*--*
```

#### SCORING:

• Test cases 1-3 satisfy N,M≤2000N,M≤2000.
• Test cases 4-8 satisfy c2>c3>⋯>cMc2>c3>⋯>cM.
• Test cases 9-15 satisfy N≤2⋅105N≤2⋅105.
• Test cases 16-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

## Solution

Let ansy(x)ansy(x) denote the minimum cost to go from (1,1)(1,1) to (x,y)(x,y). The key observation is that for a fixed yy, the function ansyansy is concave up. Specifically, ansy[x]−ansy[x−1]≤ansy[x+1]−ansy[x]ansy[x]−ansy[x−1]≤ansy[x+1]−ansy[x].

To get ansy+1ansy+1 from ansyansy, we must

1. Set ansy+1(x)=ansy(x)+x2ansy+1(x)=ansy(x)+x2 for all xx.
2. Set ansy+1(x)=min(ansy+1(x),ansy+1(x−1)+cx)ansy+1(x)=min(ansy+1(x),ansy+1(x−1)+cx) for all xx.

The latter operation is equivalent to replacing a suffix of ansy+1ansy+1 with a straight line.

We can maintain the piecewise quadratic function ansyansy with a stack (similarly to convex hull trick). Whenever we perform the second operation, we pop some elements off the top of the stack and add a new element. To answer a query (x,y)(x,y), binary search on the stack corresponding to ansyansy to find the piece of the function that corresponds to xx and evaluate it.

```#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define f first
#define s second

template<class T, class U> T fstTrue(T lo, T hi, U f) {
hi ++; assert(lo <= hi); // assuming f is increasing
while (lo < hi) { // find first index such that f is true
T mid = lo+(hi-lo)/2;
f(mid) ? hi = mid : lo = mid+1;
}
return lo;
}

ll sq(ll x) { return x*x; }

int N,M;
vector<pair<int,int>> todo;

int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N >> M;
vector<ll> C(M); for (ll& t: C) cin >> t;
int Q; cin >> Q;
vector<ll> ans(Q);
for (int i = 0; i < Q; ++i) {
int x,y; cin >> x >> y; --y;
todo[y].push_back({x,i});
}
vector<pair<int,pair<int,ll>>> stk;
for (int col = 0; col < M; ++col) {
auto eval_pair = [&](const pair<int,ll>& a, ll x) {
int pre_col = a.f;
return sq(x)*(col-pre_col)+x*C[pre_col]+a.s;
};
auto eval = [&](int x) -> ll { // binary search to find corresponding stack element
int fst_ind = fstTrue(0,(int)stk.size()-1,[&](int ind) {
return stk[ind].f >= x; });
return eval_pair(stk[fst_ind].s,x); // evaluate stack element at x
};
if (col) {
while (stk.size() > 1) { // pop off stack
int x = end(stk)[-2].f;
pair<int,ll> lst = stk.back().s;
ll val_at_x =          eval_pair(lst,x);
ll val_at_x_plus_one = eval_pair(lst,x+1);
if (val_at_x+C[col] < val_at_x_plus_one) {
stk.pop_back();
continue;
}
stk.back().f = fstTrue(x+1,stk.back().f-1,[&](int mid) {
return eval_pair(lst,mid)+C[col] < eval_pair(lst,mid+1); });
break;
}
if (stk.back().f < N) { // add to stack
int x = stk.back().f;
stk.push_back({N,{col,eval_pair(stk.back().s,x)-x*C[col]}});
}
} else { // initialize stack
stk.push_back({1,{0,-C}});
stk.push_back({N,{0,-C}});
}
for (pair<int,int> t: todo[col]) // answer all queries with y=col+1
ans[t.s] = eval(t.f);
}
for (ll t: ans) cout << t << "\n";
}```