Submission #365600

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
365600	2021-02-11T23:24:54 Z	rqi	Maxcomp (info1cup18_maxcomp)	C++14	100 / 100	438 ms	21484 KB

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.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12140 KB	Output is correct
2	Correct	8 ms	12140 KB	Output is correct
3	Correct	7 ms	12140 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	2 ms	876 KB	Output is correct
10	Correct	2 ms	1024 KB	Output is correct
11	Correct	2 ms	876 KB	Output is correct
12	Correct	2 ms	896 KB	Output is correct
13	Correct	2 ms	876 KB	Output is correct
14	Correct	2 ms	1004 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	7 ms	12140 KB	Output is correct
10	Correct	8 ms	12140 KB	Output is correct
11	Correct	7 ms	12140 KB	Output is correct
12	Correct	2 ms	876 KB	Output is correct
13	Correct	2 ms	1024 KB	Output is correct
14	Correct	2 ms	876 KB	Output is correct
15	Correct	2 ms	896 KB	Output is correct
16	Correct	2 ms	876 KB	Output is correct
17	Correct	2 ms	1004 KB	Output is correct
18	Correct	422 ms	20588 KB	Output is correct
19	Correct	432 ms	20716 KB	Output is correct
20	Correct	416 ms	20460 KB	Output is correct
21	Correct	432 ms	20652 KB	Output is correct
22	Correct	424 ms	20588 KB	Output is correct
23	Correct	418 ms	20716 KB	Output is correct
24	Correct	438 ms	21484 KB	Output is correct