7975번: 버스 여행

https://www.acmicpc.net/problem/7975

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MX = 1e3;
ll bit[4][MX * 2], dp[MX*MX];
int n, m;
struct st {
    int a, c, x, y;
}s[MX*MX];
void update(int h, int t, ll s) {
    for (; h < n + m; h += h&-h)
        bit[t][h] = max(bit[t][h], s);
}
ll query(int h, int t) {
    ll res = -2e3;
    for (; h; h -= h&-h) res = max(res, bit[t][h]);
    return res;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n*m; i++) scanf("%d", &s[i].a);
    for (int i = 0; i < n*m; i++) {
        scanf("%d", &s[i].c);
        s[i].x = i / m;
        s[i].y = i % m;
        if (!s[i].a) s[i].c = -2000;
    }
    sort(s, s + n*m, [](st i, st j) {return i.a < j.a; });
    fill(&bit[0][0], &bit[3][MX * 2], -2000LL);
    for (int i = 0, j = 0; i < n*m; i = j) {
        for (; j < n*m&&s[i].a == s[j].a; j++);
        for (int k = i; k < j; k++) {
            dp[k] = s[k].c + max({ 0LL,
                query(s[k].x + s[k].y + 1,0) + s[k].x + s[k].y,
                query(s[k].x + m - s[k].y,1) + s[k].x - s[k].y + m - 1,
                query(n - s[k].x + s[k].y,2) - s[k].x + s[k].y + n - 1,
                query(n - s[k].x + m - s[k].y - 1,3) - s[k].x - s[k].y + n + m - 2 });
        }
        for (int k = i; k < j; k++) {
            update(s[k].x + s[k].y + 1, 0, dp[k] - s[k].x - s[k].y);
            update(s[k].x + m - s[k].y, 1, dp[k] - s[k].x + s[k].y - m + 1);
            update(n - s[k].x + s[k].y, 2, dp[k] + s[k].x - s[k].y - n + 1);
            update(n - s[k].x + m - s[k].y - 1, 3, dp[k] + s[k].x + s[k].y - n - m + 2);
        }
    }
    printf("%lld", *max_element(dp, dp + n*m));
    return 0;
}