Submission #365600

#	Time	Username	Problem	Language	Result	Execution time	Memory
365600		rqi	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	438 ms	21484 KiB

maxcomp

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9+1e7;

const int mx = 1005;

void ckmax(int& a, int b){
	a = max(a, b);
}

int N, M;
int A[mx][mx];
int nA[mx][mx];

void rot(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			nA[M+1-j][i] = A[i][j];
		}
	}
	swap(N, M);
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			A[i][j] = nA[i][j];
		}
	}
}

int maxSub[mx][mx];

int getAns(){
	for(int i = 0; i <= N; i++){
		for(int j = 0; j <= M; j++){
			maxSub[i][j] = -INF;
		}
	}
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			maxSub[i][j] = -A[i][j]+i+j;
		}
	}

	int ans = -INF;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			ckmax(maxSub[i][j], max(maxSub[i-1][j], max(maxSub[i][j-1], maxSub[i-1][j-1])));
			//cout << maxSub[i][j] << " ";
			ckmax(ans, A[i][j]-i-j+maxSub[i][j]-1);
		}
		//cout << "\n";
	}

	return ans;
}

int main(){
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cin >> A[i][j];
		}
	}
	int ans = -INF;
	for(int i = 0; i < 4; i++){
		ckmax(ans, getAns());
		rot();
	}
	cout << ans << "\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40