比赛 EYOI与SBOI开学欢乐赛2nd 评测结果 AAAAAAAAA
题目名称 最佳游览 最终得分 100
用户昵称 lihaoze 运行时间 0.003 s
代码语言 C++ 内存使用 1.59 MiB
提交时间 2022-09-02 21:43:10
显示代码纯文本
#include <bits/stdc++.h>

const int N = 20010, M = 110;
int a[M][N];
int mx[N], dp[N], ans;

int main() {
	freopen("perfecttour.in", "r", stdin);
	freopen("perfecttour.out", "w", stdout);
	int n, m;
	std::cin >> n >> m, -- m;
	for (int i = 1; i <= m; ++ i) mx[i] = -1e9;
	for (int i = 1; i <= n; ++ i) 
		for (int j = 1; j <= m; ++ j)
			std::cin >> a[i][j], mx[j] = std::max(a[i][j], mx[j]);
	for (int i = 1; i <= m; ++ i) {
		dp[i] = std::max(0, dp[i - 1]) + mx[i];
		ans = std::max(dp[i], ans);
	}
	std::cout << ans << '\n';
	return 0;
}