Upgrading Technology

There are multiple test cases. The first line contains an integer T ( $1 \leq T \leq 10$ ), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers n, m ( $1 \leq n, m \leq 1000$ ), representing the number of technologies and the number of levels respectively.

The i-th of the next n lines contains m integers, where the j-th number is $c_{i j}$ ( $-10^{9} \leq c_{i j} \leq 10^{9}$ ).

The last line contains m integers, where the j-th number is $d_{j}$ ( $-10^{9} \leq d_{j} \leq 10^{9}$ ).

We ensure that the sum of $n \cdot m$ in all test cases is at most $2 \times 10^{6}$ .

C++14(g++5.4) 解法, 执行用时: 1580ms, 内存消耗: 20364K, 提交时间: 2019-08-04 11:07:56

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;i++)
typedef long long ll;
const ll mod=10010;

int a[1010][1010],b[1010];
int n,m;
ll s[1010][1010];
int main(){
	int T;
	cin>>T;
	rep(kase,1,T){
		cin>>n>>m;
		rep(i,1,n)rep(j,1,m){
			cin>>a[i][j];
			a[i][j]=-a[i][j];
		}
		rep(i,1,m)cin>>b[i];
		rep(i,1,n){
			s[i][m]=0;
			for(int j=m-1;j>=0;j--)
				s[i][j]=max(0ll,s[i][j+1]+a[i][j+1]);
		}
		ll ans=0,now=0;
		rep(j,0,m){
			ll cnt=0,minn=1e18;
			now+=b[j];
			rep(i,1,n){
				now+=a[i][j];
				cnt+=s[i][j];
				minn=min(minn,s[i][j]);
			}
			ans=max(ans,cnt-minn+now);
		}
		cout<<"Case #"<<kase<<": "<<ans<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 498ms, 内存消耗: 16204K, 提交时间: 2019-08-03 20:43:24

#include<bits/stdc++.h>
#define maxn 1005
#define LL long long
using namespace std;
int T,n,m,x;
LL ans,sum,D,s[maxn][maxn],Min[maxn][maxn];
int main() {
	scanf("%d",&T);
	for(int _=1; _<=T; _++) {
		scanf("%d %d",&n,&m);
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=m; j++)
				scanf("%d",&x),s[i][j]=s[i][j-1]+x;
			Min[i][m+1]=1ll<<60;
			for(int j=m; j>=0; j--) Min[i][j]=min(Min[i][j+1],s[i][j]);
		}
		ans=D=0;
		for(int j=0; j<=m; j++) {
			if(j) scanf("%d",&x),D+=x;
			sum=1ll<<60;
			for(int i=1; i<=n; i++) if(s[i][j]-Min[i][j]<sum) sum=s[i][j]-Min[i][j];
			for(int i=1; i<=n; i++) sum+=Min[i][j];
			ans=max(ans,D - sum);
		}
		printf("Case #%d: %lld\n",_,ans);
	}
}

详情