oj.uz

Submission #497737

# Submission time Handle Problem Language Result Execution time Memory
497737 2021-12-23T17:16:18 Z Ziel Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 166 ms 112392 KB 
/**
 * LES GREATEABLES BRO TEAM
**/
 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
#define sz(x) (int)x.size()
const bool FLAG = false;
void setIO(const string &f = "");
 
string to_string(const string s) {
	return '"' + s + '"';
}
string to_string(const char c) {
 	return char(39) + string(1, c) + char(39);
}
string to_string(const char* s) {
 	return to_string(string(s));
}
string to_string(bool f) {
	return (f ? "true" : "false");
}
template<class A, class B>
string to_string(const pair<A, B> x) {
	return "(" + to_string(x.first) + ", " + to_string(x.second) + ")";
}
template<class A, class B, class C>
string to_string(const tuple<A, B, C> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ")";
}
template<class A, class B, class C, class D>
string to_string(const tuple<A, B, C, D> x) {
	return "(" + to_string(get<0>(x)) + ", " + to_string(get<1>(x)) + ", " + to_string(get<2>(x)) + ", " + to_string(get<3>(x)) + ")";
}
template<class T>
string to_string(const T v) {
	string res = "{"; bool f = true;
	for (auto x: v)
		res += (f ? to_string(x) : ", " + to_string(x)), f = false;
	return res + "}";
}
void debug_args() { cerr << "]\n"; }
template<class H, class... T>
void debug_args(H x, T... y) {
	cerr << to_string(x);
	if (sizeof... (y))
	cerr << ", ";
	debug_args(y...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: [", debug_args(__VA_ARGS__);
#else
#define debug(...) 47
#endif
 
#define int ll
const int INF = 1e14 + 123;
ll dp[5][1200][1200], mn[5][1200][1200], a[1200][1200];

void solve() {
    int n, m;
    cin >> n >> m;
   	for (int i = 1; i <= n; i++)
   		for (int j = 1; j <= m; j++)
   			cin >> a[i][j];
   	
   	auto relax_min = [](int &x, int y) {
   		if (x > y) {
   			x = y;
   			return true;
   		}
   		return false;
   	};
   	auto relax_max = [](int &x, int y) {
   		if (x < y) {
   			x = y;
   			return true;
   		}
   		return false;
   	};
   	for (int k = 0; k <= 4; k++) {
   		for (int i = 0; i <= n + 1; i++) {
   			for (int j = 0; j <= m + 1; j++) {
   				dp[k][i][j] = INF;
   				mn[k][i][j] = INF;
   			}
   		}
   	}
   	for (int i = 1; i <= n; i++)
   		for (int j = 1; j <= m; j++)
   			dp[0][i][j] = a[i][j] - i - j,
   			mn[0][i][j] = min({dp[0][i][j], mn[0][i - 1][j], mn[0][i][j - 1]});
	
	for (int i = 1; i <= n; i++)
   		for (int j = m; j >= 1; j--)
   			dp[1][i][j] = a[i][j] - i + j,
   			mn[1][i][j] = min({dp[1][i][j], mn[1][i - 1][j], mn[1][i][j + 1]});
	
	for (int i = n; i >= 1; i--)
   		for (int j = 1; j <= m; j++)   			
   			dp[2][i][j] = a[i][j] + i - j,
   			mn[2][i][j] = min({dp[2][i][j], mn[2][i + 1][j], mn[2][i][j - 1]});
	
	for (int i = n; i >= 1; i--)
   		for (int j = m; j >= 1; j--)
   			dp[3][i][j] = a[i][j] + i + j,
   			mn[3][i][j] = min({dp[3][i][j], mn[3][i + 1][j], mn[3][i][j + 1]});
   	
   	ll ans = -1;
   	for (int i = 1; i <= n; i++) {
   		for (int j = 1; j <= m; j++) {
   			ans = max(ans, dp[0][i][j] - mn[0][i][j] - 1);
   			ans = max(ans, dp[1][i][j] - mn[1][i][j] - 1);
   			ans = max(ans, dp[2][i][j] - mn[2][i][j] - 1);
   			ans = max(ans, dp[3][i][j] - mn[3][i][j] - 1);
   		}
   	}

   	cout << ans;
}
 
signed main() {
    setIO();
    
    int tt = 1;
    if (FLAG) {
    	cin >> tt;
    }
    while (tt--) {
    	solve();
    }
    
    return 0;
}
 
void setIO(const string &f) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen((f + ".in").c_str(), "r")) {
        freopen((f + ".in").c_str(), "r", stdin);
        freopen((f + ".out").c_str(), "w", stdout);
    }
}

Compilation message

maxcomp.cpp: In function 'void solve()':
maxcomp.cpp:71:10: warning: variable 'relax_min' set but not used [-Wunused-but-set-variable]
   71 |     auto relax_min = [](int &x, int y) {
      |          ^~~~~~~~~
maxcomp.cpp:78:10: warning: variable 'relax_max' set but not used [-Wunused-but-set-variable]
   78 |     auto relax_max = [](int &x, int y) {
      |          ^~~~~~~~~
maxcomp.cpp: In function 'void setIO(const string&)':
maxcomp.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maxcomp.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 580 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 576 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 580 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 576 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 3 ms 2768 KB Output is correct
11 Correct 2 ms 2892 KB Output is correct
12 Correct 2 ms 2760 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 1 ms 2772 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 1 ms 580 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 576 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 688 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 3 ms 2768 KB Output is correct
14 Correct 2 ms 2892 KB Output is correct
15 Correct 2 ms 2760 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 1 ms 2772 KB Output is correct
18 Correct 156 ms 112364 KB Output is correct
19 Correct 163 ms 112356 KB Output is correct
20 Correct 166 ms 111980 KB Output is correct
21 Correct 154 ms 112392 KB Output is correct
22 Correct 149 ms 112320 KB Output is correct
23 Correct 154 ms 112300 KB Output is correct
24 Correct 145 ms 108056 KB Output is correct