滴滴笔试第二题

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static  int[][] arr;
    static  long[][] memo;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int n = in.nextInt();
        int m = in.nextInt();
        //n 奖励点数
        arr = new int[n][s];
        for(int i = 0;i < s;i++){
            for(int j = 0;j < n;j++){
                arr[j][i] = in.nextInt();
            }
        }
        for(int[] x : arr){
            Arrays.sort(x);
        }
        memo = new long[n][m + 1];
        for (int i = 0;i < n;i++){
            Arrays.fill(memo[i],-1);
        }
        System.out.println(dfs(0,m));
    }
    public static long dfs(int i,int m){
        if(m < 0) return Integer.MAX_VALUE / 2;
        if(i >= arr.length) return 0;
        if(memo[i][m] != - 1) return memo[i][m];
        long res = dfs(i + 1,m);
        //投资
        int[] x = arr[i];
        for(int j = 0;j < x.length;j++){
            if(m > 2 * x[j]){
                res = Math.max(res,dfs(i + 1,m - 2 * x[j] - 1) + (long)(j + 1) * (i + 1));
            }
        }
        return memo[i][m] = res;
    }
}