oj.uz

Submission #676033

# Submission time Handle Problem Language Result Execution time Memory
676033 2022-12-29T01:12:37 Z thiago_bastos Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 133 ms 25440 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

const int N = 1e3 + 10;

int a[N][N], tmp[N][N], n, m;
i64 ps[N][N];

void rotate() {
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			tmp[j][n - i - 1] = a[i][j];

	swap(n, m);

	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			a[i][j] = tmp[i][j];
}

void solve() {
	i64 ans = -INFLL;

	cin >> n >> m;

	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			cin >> a[i][j];

	for(int i = 0; i <= max(n, m); ++i) ps[0][i] = ps[i][0] = INFLL;

	for(int k = 0; k < 4; ++k) {
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= m; ++j) {
				ps[i][j] = a[i - 1][j - 1] - i - j;
				ps[i][j] = min(ps[i][j], ps[i - 1][j]);
				ps[i][j] = min(ps[i][j], ps[i][j - 1]);
				ans = max(ans, -i - j + a[i - 1][j -1] - ps[i][j] - 1);
			}
		}
		rotate();
	}

	cout << ans << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12268 KB Output is correct
2 Correct 5 ms 12244 KB Output is correct
3 Correct 6 ms 12244 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 980 KB Output is correct
11 Correct 1 ms 976 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 984 KB Output is correct
14 Correct 1 ms 852 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 5 ms 12268 KB Output is correct
10 Correct 5 ms 12244 KB Output is correct
11 Correct 6 ms 12244 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 980 KB Output is correct
14 Correct 1 ms 976 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 984 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 115 ms 24596 KB Output is correct
19 Correct 133 ms 24696 KB Output is correct
20 Correct 111 ms 24288 KB Output is correct
21 Correct 117 ms 24656 KB Output is correct
22 Correct 126 ms 24556 KB Output is correct
23 Correct 112 ms 24600 KB Output is correct
24 Correct 123 ms 25440 KB Output is correct