模拟 + 二维st表

枚举每一次所有技能全部到达的level，然后分别对每个技能花费为负的情况往上加，前提是至少有一个不能加，因为可能下一次的全部技能到达的level拿到的收益是个负数。

每次枚举都不拿多的d才可以可以遍历所有情况。

分别枚举每个技能的最小cost的时候，可以用st表来维护前缀和。

#include 
    
     #define INF 23333333333333333#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 2000;int n, m, d[N], _, c[N][N], cnt[N], cs, lb[N];LL pre[N][N], st[N][N][11], b[N];LL query(int k, int l, int r){    int t = lb[r - l + 1];    return min(st[k][l][t], st[k][r - (1 << t) + 1][t]);}int main(){    lb[0] = -1; for(int i = 1; i < N; i ++) lb[i] = lb[i>>1] + 1;    for(scanf("%d", &_); _; _ --){        scanf("%d%d", &n, &m);        for(int i = 1; i <= n; i ++){            for(int j = 1; j <= m; j ++) scanf("%d", &c[i][j]);        }        for(int i = 1; i <= m; i ++) scanf("%d", &d[i]);        for(int i = 1; i <= n; i ++){            for(int j = 1; j <= m; j ++) pre[i][j] = pre[i][j - 1] + c[i][j];        }        for(int i = 1; i <= m; i ++) b[i] = b[i - 1] + d[i];        for(int i = 1; i <= n; i ++){            for(int j = 1; j <= m; j ++) st[i][j][0] = pre[i][j];        }        for(int k = 1; k <= n; k ++){            for(int j = 1; j < 11; j ++){                for(int i = 1; (1 << j) + i - 1 <= m; i ++)                    st[k][i][j] = min(st[k][i][j - 1], st[k][i + (1 << (j - 1))][j - 1]);            }        }        vector
      
        ans;        for(int k = 0; k <= m; k ++){            LL val = b[k];            for(int i = 1; i <= n; i ++) val -= pre[i][k];            if(k != m){                LL sub = -INF;                bool flag = false;                for(int i = 1; i <= n; i ++){                    // k + 1...m minimum cost                    LL x = query(i, k + 1, m) - pre[i][k];                    sub = max(sub, x);                    if(x > 0) flag = true;                    if(x <= 0) val -= x;                }                if(!flag) val += sub;            }            ans.pb(val);        }        printf("Case #%d: %lld\n", ++cs, *max_element(ans.begin(), ans.end()));    }    return 0;}