蒟蒻求复杂度
查看原帖
蒟蒻求复杂度
1124323
A_small_WA楼主2024/6/11 23:03

rt, 以下是代码:

#include <bits/stdc++.h>
using namespace std;
long long l[200005],sum[200005];
int main(){
	long long m,n,k,ans=-10000000;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			cin>>k;
			if(i==1) l[j]=k;
			else l[j]=max(l[j],k);
			if(i==m) sum[j]=sum[j-1]+l[j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=n;j>=i;j--){
			ans=max(sum[j]-sum[i-1],ans);
		}
	}
	cout<<ans;
	return 0;
}

题目数据在 n≤2000×104n\le2000\times10^4 左右,我的代码应该是 O(n2)O(n^2) 的,为什么还能 AC?求大佬解答。

2024/6/11 23:03
加载中...