oj.uz

Submission #464797

# Submission time Handle Problem Language Result Execution time Memory
464797 2021-08-14T07:21:52 Z hhhhaura Maxcomp (info1cup18_maxcomp) C++14
30 / 100
 500 ms 368 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 1e9
#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:19:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
maxcomp.cpp:19:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 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 48 ms 332 KB Output is correct
2 Correct 47 ms 332 KB Output is correct
3 Correct 47 ms 332 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Execution timed out 680 ms 368 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 48 ms 332 KB Output is correct
10 Correct 47 ms 332 KB Output is correct
11 Correct 47 ms 332 KB Output is correct
12 Execution timed out 680 ms 368 KB Time limit exceeded
13 Halted 0 ms 0 KB -