oj.uz

Submission #464795

# Submission time Handle Problem Language Result Execution time Memory
464795 2021-08-14T07:20:52 Z hhhhaura Maxcomp (info1cup18_maxcomp) C++14
30 / 100
 500 ms 452 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

using namespace std;

#define INF 1000000000000000000
#define int long long int
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);} 
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	int n, m;
	vector<vector<int>> a, dis, vis;
	vector<int> dirx = {0, 0, 1, -1};
	vector<int> diry = {1, -1, 0, 0};
	vector<int> v;
	void init_(int _n, int _m) {
		n = _n, m = _m;
		a.assign(n, vector<int>(m, 0));
	}
	void update(int x, int y) {
		vis[x][y] = 1;
		rep(i, 0, 3) {
			int nx = x + dirx[i], ny = y + diry[i];
			if(nx < 0 || ny < 0 || nx >= n || ny >= m || !vis[nx][ny]) continue;
			dis[x][y] = min(dis[x][y], dis[nx][ny] + 1);
		}
		queue<int> q; 
		q.push(x * m + y);
		while(q.size()) {
			int cur = q.front(); q.pop();
			int cx = cur / m, cy = cur % m;
			rep(i, 0, 3) {
				int nx = cx + dirx[i], ny = cy + diry[i];
				if(nx < 0 || ny < 0 || nx >= n || ny >= m || !vis[nx][ny]) continue;
				if(dis[cx][cy] + 1 < dis[nx][ny]) {
					dis[nx][ny] = dis[cx][cy] + 1;
					q.push(nx * m + ny);
				}
			}
		}
		return;
	}
	int solve() {
		vector<pii> b;
		rep(i, 0, n - 1) rep(j, 0, m - 1) {
			b.push_back({a[i][j], i * m + j});
			v.push_back(a[i][j]);
		}	
		sort(all(v));
		v.resize(unique(all(v)) - v.begin());
		sort(all(b));
		int sz = v.size(), ans = -INF, x, y, ii = 0, jj, pre;
		rep(i, 0, sz - 1) {
			dis.assign(n, vector<int>(m, INF));
			vis.assign(n, vector<int>(m, 0));
			while(ii < n * m && v[i] == b[ii].first) {
				x = b[ii].second / m, y = b[ii].second % m;
				dis[x][y] = 0, vis[x][y] = 1, ii++;
			}
			jj = ii;
			rep(j, i + 1, sz - 1) {
				pre = jj;
				while(jj < n * m && v[j] == b[jj].first) {
					x = b[jj].second / m, y = b[jj].second % m;
					update(x, y), jj++;
				}
				rep(kk, pre, jj - 1) {
					x = b[kk].second / m, y = b[kk].second % m;
					ans = max(ans, v[j] - v[i] - dis[x][y] - 1);
				}
			}
		}
		return ans;
	}

};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	init_(n, m);
	rep(i, 0, n - 1) rep(j, 0, m - 1) {
		cin >> a[i][j];
	}
	cout << solve() << "\n";
	return 0;
}

Compilation message

maxcomp.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
maxcomp.cpp:20:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
maxcomp.cpp:20:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 332 KB Output is correct
2 Correct 46 ms 372 KB Output is correct
3 Correct 48 ms 364 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Execution timed out 690 ms 452 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 49 ms 332 KB Output is correct
10 Correct 46 ms 372 KB Output is correct
11 Correct 48 ms 364 KB Output is correct
12 Execution timed out 690 ms 452 KB Time limit exceeded
13 Halted 0 ms 0 KB -