1627E - Not Escaping - CodeForces Solution

# include <bits/stdc++.h>
using namespace std;

# define int long long
# define f(i,a,b) for(int i = a; i <= b; i ++)
# define g(i,b,a) for(int i = b; i >= a; i --)
# define CI const int

CI maxn = 2e5 + 7;

/*
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why???
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why???
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why???
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why???
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why???
Why???Why???Why???Why???Why???Why???Why???Why???Why???Why??? 
*/

int n, m, k;
int x[maxn];
int a[maxn], b[maxn], c[maxn], d[maxn], h[maxn];
vector <int> row[maxn];
int dp[maxn];

struct Node {
    int x, y, id;
    vector <pair <int, int> > ladder;
    bool operator < (const Node &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
}t[maxn * 2];

int tot;
int mp[maxn * 2];

void solve() {
    cin >> n >> m >> k;
    f (i, 1, n)
        scanf("%lld", &x[i]);
    f (i, 1, k)
        scanf("%lld %lld %lld %lld %lld", &a[i], &b[i], &c[i], &d[i], &h[i]);
    f (i, 1, 2 * k + 2)
        t[i].ladder.clear();
    tot = 0;
    f (i, 1, k) {
        ++ tot; t[tot] = {a[i], b[i], tot};
        ++ tot; t[tot] = {c[i], d[i], tot};
        t[tot - 1].ladder.push_back({tot, h[i]});
    }
    ++ tot; t[tot] = {1, 1, tot};
    ++ tot; t[tot] = {n, m, tot};
    sort(t + 1, t + tot + 1);
    f (i, 1, tot)
        mp[t[i].id] = i;
    f (i, 1, tot)
        for (auto &x : t[i].ladder)
            x.first = mp[x.first];
    f (i, 1, n)
        row[i].clear();
    f (i, 1, tot)
        row[t[i].x].push_back(i);
    f (i, 1, tot)
        dp[i] = 2e18;
    dp[1] = 0;
    f (i, 1, n) {
        f (j, 1, (int) row[i].size() - 1) {
            int p = row[i][j - 1];
            int q = row[i][j];
            dp[q] = min(dp[q], dp[p] + abs(t[p].y - t[q].y) * x[i]);
        }
        g (j, (int) row[i].size() - 1, 1) {
            int p = row[i][j - 1];
            int q = row[i][j];
            dp[p] = min(dp[p], dp[q] + abs(t[p].y - t[q].y) * x[i]);
        }
        for (int p : row[i])
            for (auto q : t[p].ladder)
                dp[q.first] = min(dp[q.first], dp[p] - q.second);
    }
    if (dp[tot] >= 1e18) printf("NO ESCAPE\n");
    else printf("%lld\n", dp[tot]);
}

signed main() {
    int t; cin >> t;
    while (t --) solve();
    return 0;
}