容易想到dp[i][j]表示在第i行j个路口的开始走最大高兴值。

每次可以向左走，或者向右边走，然后向北走。（或者直接往北）

向左走到，状态转移为dp[i][j] = dp[i][k] + happy[i][k][j]（为了方便处理，i从1开始编号，0行dp值存0）

处理出前缀和，happy[i][k][j]表示为sum[i][j] - sum[i][k]

向左走应该取max(dp[i][k]-sum[i][k])

k应该满足time[i][k][j] <= k

随着j的变化k的范围是一个滑动窗口，用单调队列去维护。

右边走转移 dp[i][k] + sum[i][k] - sum[i][j]，类似处理。

转移为O(1)，复杂度为O(N*M)

#include
     
      using namespace std;const int N = 102, M = 1e4+5;int n, m, k;int h[N][M], t[N][M];int dp[N][M];int q[M];//#define LOCALint main(){#ifdef LOCAL    freopen("in.txt","r",stdin);#endif    while(scanf("%d%d%d", &n, &m, &k), n+m+k){        n++;        for(int i = 1; i <= n; i++){            for(int j = 1; j <= m ;j++){                scanf("%d",h[i]+j);                h[i][j] += h[i][j-1];            }        }        for(int i = 1; i <= n; i++){            for(int j = 1; j <= m ;j++){                scanf("%d",t[i]+j);                t[i][j] += t[i][j-1];            }        }        for(int i = 1; i <= n; i++){            #define maintain(diff) while(hd
      
        k) hd++;            #define inst(val) while(hd
       
        = 0; j--){                inst(rval)                maintain(rdis)                dp[i][j] = max(dp[i][j],rval(q[hd])-h[i][j]);            }        }        int ans = 0;        for(int j = 0; j <= m; j++){            ans = max(ans,dp[n][j]);        }        printf("%d\n",ans);    }    return 0;}