oj.uz

Submission #892980

# Submission time Handle Problem Language Result Execution time Memory
892980 2023-12-26T09:33:36 Z vjudge1 Maxcomp (info1cup18_maxcomp) C++17
100 / 100
 115 ms 47824 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

//#pragma GCC optimization("g", on)
//#pragma GCC optimization("03")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse,-fgcse-lm")
//#pragma GCC optimize("-ftree-pre,-ftree-vrp")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define aboba ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define br break;
#define sp " "
#define en "\n"
#define pb push_back
#define sz size()
#define bg begin()
#define ed end()
#define in insert
#define ss second
#define ff first
#define setp(a) cout << fixed; cout << setprecision(a);
#define all(v) v.begin(), v.end()
 
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef double db;
typedef tree<
    long long,
    null_type,
    less_equal<long long>,
    rb_tree_tag,
    tree_order_statistics_node_update> orset;

void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
ll bp(ll x, ll y, ll z) { ll res = 1; while (y) { if (y & 1) { res = (res * x) % z; y--; } x = (x * x) % z; y >>= 1; } return res; }
// C(n, k) = ((fact[n] * bp(fact[k], mod - 2)) % mod * bp(fact[n - k], mod - 2)) % mod;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; }

const ll N = 3e5 + 11;
const ll inf = 1e18 + 7;
ll tt = 1;
ll a[1005][1005];
ll p[1005][1005][5];

void solve() {
	ll n, m; cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0;i <= n + 1;i++) {
		for (int j = 0;j <= m + 1;j++) {
			p[i][j][1] = p[i][j][2] = p[i][j][3] = p[i][j][4] = -inf;
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			p[i][j][1] = max({-a[i][j] + i + j, p[i - 1][j][1], p[i][j - 1][1]});
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = m;j >= 1;j--) {
			p[i][j][2] = max({-a[i][j] + i - j, p[i - 1][j][2], p[i][j + 1][2]});
		}
	}
	for (int i = n;i >= 1;i--) {
		for (int j = 1;j <= m;j++) {
			p[i][j][3] = max({-a[i][j] - i + j, p[i + 1][j][3], p[i][j - 1][3]});
		}
	}
	for (int i = n;i >= 1;i--) {
		for (int j = m;j >= 1;j--) {
			p[i][j][4] = max({-a[i][j] - i - j, p[i + 1][j][4], p[i][j + 1][4]});
		}
	}
	ll ans = -inf;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			ans = max(ans, a[i][j] - i - j + p[i][j][1]);
			ans = max(ans, a[i][j] - i + j + p[i][j][2]);
			ans = max(ans, a[i][j] + i - j + p[i][j][3]);
			ans = max(ans, a[i][j] + i + j + p[i][j][4]);
		}
	}
	cout << ans - 1 << en;
}
   
int main() {      
    aboba    
//    freopen("cownomics");
//    precalc();
//    cin >> tt;
    for (int i = 1;i <= tt;i++) {
		solve();
    }
}

Compilation message

maxcomp.cpp: In function 'void freopen(std::string)':
maxcomp.cpp:47:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
maxcomp.cpp:47:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4568 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4696 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4568 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 94 ms 47696 KB Output is correct
19 Correct 90 ms 47820 KB Output is correct
20 Correct 86 ms 47700 KB Output is correct
21 Correct 88 ms 47700 KB Output is correct
22 Correct 115 ms 47820 KB Output is correct
23 Correct 89 ms 47824 KB Output is correct
24 Correct 87 ms 47576 KB Output is correct