답안 #365600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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