oj.uz

Submission #496793

# Submission time Handle Problem Language Result Execution time Memory
496793 2021-12-22T04:34:54 Z Ziel Maxcomp (info1cup18_maxcomp) C++17
30 / 100
 38 ms 83472 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

ll dp[2505][55][55], mx[2505][55][55], mn[2505][55][55], a[55][55];

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];
   	
   	memset(dp, -1, sizeof(dp));
   	auto relax = [](ll &x, ll y) {
   		if (x < y) {
   			x = y;
   			return true;
   		}
   		return false;
   	};
   	if (n != 1) {
	   	for (int k = 1; k <= n + m; k++) {
   			for (int i = 1; i <= n; i++) {
   				for (int j = 1; j <= m; j++) {
   					if (k == 1) {
   						mx[k][i][j] = a[i][j];
   						mn[k][i][j] = a[i][j];
	   					dp[k][i][j] = mx[k][i][j] - mn[k][i][j] - k;
   					} else {
   						mx[k][i][j] = -1;
   						mn[k][i][j] = -1;
   						if (i - 1 >= 1 && mx[k - 1][i - 1][j] != -1 && mn[k - 1][i - 1][j] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i - 1][j]) - min(a[i][j], mn[k - 1][i - 1][j]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i - 1][j]);
   							mn[k][i][j] = min(a[i][j], mn[k - 1][i - 1][j]);
	   					}
   						if (j - 1 >= 1 && mx[k - 1][i][j - 1] != -1 && mn[k - 1][i][j - 1] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i][j - 1]) - min(a[i][j], mn[k - 1][i][j - 1]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i][j - 1]);
   							mn[k][i][j] = min(a[i][j], mn[k - 1][i][j - 1]);
   						}
   						if (i + 1 <= n && mx[k - 1][i + 1][j] != -1 && mn[k - 1][i + 1][j] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i + 1][j]) - min(a[i][j], mn[k - 1][i + 1][j]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i + 1][j]);
	   						mn[k][i][j] = min(a[i][j], mn[k - 1][i + 1][j]);
   						}
   						if (j + 1 <= m && mx[k - 1][i][j + 1] != -1 && mn[k - 1][i][j + 1] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i][j + 1]) - min(a[i][j], mn[k - 1][i][j + 1]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i][j + 1]);
   							mn[k][i][j] = min(a[i][j], mn[k - 1][i][j + 1]);
   						}
	   				}
   				}
   			}
	   	}
	} else {
		for (int k = 1; k <= n + m; k++) {
   			for (int i = 1; i <= n; i++) {
   				for (int j = 1; j <= m; j++) {
   					if (k == 1) {
   						mx[k][i][j] = a[i][j];
   						mn[k][i][j] = a[i][j];
	   					dp[k][i][j] = mx[k][i][j] - mn[k][i][j] - k;
   					} else {
   						mx[k][i][j] = -1;
   						mn[k][i][j] = -1;
   						if (i - 1 >= 1 && mx[k - 1][i - 1][j] != -1 && mn[k - 1][i - 1][j] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i - 1][j]) - min(a[i][j], mn[k - 1][i - 1][j]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i - 1][j]);
   							mn[k][i][j] = min(a[i][j], mn[k - 1][i - 1][j]);
	   					}
   						if (j - 1 >= 1 && mx[k - 1][i][j - 1] != -1 && mn[k - 1][i][j - 1] != -1 && relax(dp[k][i][j], max(a[i][j], mx[k - 1][i][j - 1]) - min(a[i][j], mn[k - 1][i][j - 1]) - k)) {
	   						mx[k][i][j] = max(a[i][j], mx[k - 1][i][j - 1]);
   							mn[k][i][j] = min(a[i][j], mn[k - 1][i][j - 1]);
   						}
	   				}
   				}
   			}
	   	}
	}
   	ll res = -1;
   	for (int k = 1; k <= n + m; k++) {
   		for (int i = 1; i <= n; i++) {
   			for (int j = 1; j <= m; j++) {
   				relax(res, dp[k][i][j]);
   			}
   		}
   	}
   	cout << res;
}

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 setIO(const string&)':
maxcomp.cpp:163:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         freopen((f + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maxcomp.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |         freopen((f + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 59724 KB Output is correct
2 Correct 21 ms 59700 KB Output is correct
3 Correct 22 ms 59724 KB Output is correct
4 Correct 23 ms 59736 KB Output is correct
5 Correct 22 ms 59640 KB Output is correct
6 Correct 28 ms 59736 KB Output is correct
7 Correct 22 ms 59624 KB Output is correct
8 Correct 22 ms 59724 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 83472 KB Output is correct
2 Correct 38 ms 83308 KB Output is correct
3 Correct 33 ms 83268 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 59724 KB Output is correct
2 Correct 21 ms 59700 KB Output is correct
3 Correct 22 ms 59724 KB Output is correct
4 Correct 23 ms 59736 KB Output is correct
5 Correct 22 ms 59640 KB Output is correct
6 Correct 28 ms 59736 KB Output is correct
7 Correct 22 ms 59624 KB Output is correct
8 Correct 22 ms 59724 KB Output is correct
9 Incorrect 26 ms 64388 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 59724 KB Output is correct
2 Correct 21 ms 59700 KB Output is correct
3 Correct 22 ms 59724 KB Output is correct
4 Correct 23 ms 59736 KB Output is correct
5 Correct 22 ms 59640 KB Output is correct
6 Correct 28 ms 59736 KB Output is correct
7 Correct 22 ms 59624 KB Output is correct
8 Correct 22 ms 59724 KB Output is correct
9 Correct 38 ms 83472 KB Output is correct
10 Correct 38 ms 83308 KB Output is correct
11 Correct 33 ms 83268 KB Output is correct
12 Incorrect 26 ms 64388 KB Output isn't correct
13 Halted 0 ms 0 KB -