比赛 EYOI与SBOI开学欢乐赛2nd 评测结果 AAAAAAAAA
题目名称 最佳游览 最终得分 100
用户昵称 Tab↹ 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-09-02 21:21:36
显示代码纯文本
#include <iostream>
#include <fstream>
#include <climits>

using namespace std;


int main(void) {
    ifstream fin("perfecttour.in");
    ofstream fout("perfecttour.out");
    int n, m;
    int** mat;
    int* arr;
    int* dp;
    fin >> n >> m;
    arr = new int[m+1]{};
    dp  = new int[m+1]{};
    mat = new int*[n+1];
    --m;
    for(int i = 1; i <= n; ++i) {
        mat[i] = new int[m+1];
        for(int j = 1; j <= m; ++j) {
            fin >> mat[i][j];
        }
    }
    for(int mx, i = 1; i <= m; ++i) {
        mx = INT_MIN;
        for(int j = 1; j <= n; ++j) {
            if(mat[j][i] > mx)
                mx = mat[j][i];
        }
        arr[i] = mx;
    }

    dp[0] = 0;
    int ans = INT_MIN;
    for(int i = 1; i <= m; ++i) {
        if(dp[i-1] > 0)
            dp[i] = dp[i-1] + arr[i];
        else
            dp[i] = arr[i];
        if(dp[i] > ans)
            ans = dp[i];
    }

    fout << ans;

    delete []dp;
    delete []arr;
    return 0;
}