oj.uz

Submission #210936

# Submission time Handle Problem Language Result Execution time Memory
210936 2020-03-19T02:47:42 Z ryansee Maxcomp (info1cup18_maxcomp) C++14
100 / 100
 328 ms 28712 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef int ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF INF //((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (1006)
int n,m,dist[MAXN][MAXN],grid[MAXN][MAXN],ans=-LLINF;
#define gc getchar_unlocked
void in(int &x){
	x=0;
	char ch=gc();
	while(ch<'0'||ch>'9')ch=gc();
	while(ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-48;
		ch=gc();
	}
}
vector<spi> v;
int main(){
	// FAST
	in(n),in(m);
	FOR(i,1,n)FOR(j,1,m)in(grid[i][j]);
	queue<pi> pq;
	FOR(i,1,n)FOR(j,1,m)v.eb(grid[i][j]-1,pi(i,j));
	sort(all(v));
	ll dx[]={0,0,1,-1};
	ll dy[]={1,-1,0,0};
	mmst(dist,-1);
	while(pq.size()||v.size()){
		ll x,y,d;
		if(v.empty() || (pq.size() && dist[pq.front().f][pq.front().s] >= v.back().f)) x=pq.front().f,y=pq.front().s,d=dist[x][y],pq.pop();
		else x=v.back().s.f,y=v.back().s.s,d=v.back().f,dist[x][y]=v.back().f,v.pop_back();
		if(dist[x][y]^d)continue;
		ans=max(ans,d-grid[x][y]);
		FOR(i,0,3){
			ll nx=x+dx[i];
			ll ny=y+dy[i];
			if(nx<=0||nx>n||ny<=0||ny>m)continue;
			if(dist[nx][ny]==-1){
				dist[nx][ny]=d-1;
				if(dist[nx][ny]<ans)continue;
				pq.emplace(pi(nx,ny));
			}else assert(dist[nx][ny]>=d-1);
		}
	}
	cout<<ans<<'\n';
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 7 ms 4352 KB Output is correct
3 Correct 8 ms 4352 KB Output is correct
4 Correct 9 ms 4352 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 8 ms 4352 KB Output is correct
7 Correct 8 ms 4352 KB Output is correct
8 Correct 7 ms 4352 KB Output is correct
9 Correct 7 ms 4608 KB Output is correct
10 Correct 7 ms 4608 KB Output is correct
11 Correct 8 ms 4608 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 8 ms 4608 KB Output is correct
14 Correct 7 ms 4608 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4352 KB Output is correct
2 Correct 7 ms 4352 KB Output is correct
3 Correct 8 ms 4352 KB Output is correct
4 Correct 9 ms 4352 KB Output is correct
5 Correct 7 ms 4352 KB Output is correct
6 Correct 8 ms 4352 KB Output is correct
7 Correct 8 ms 4352 KB Output is correct
8 Correct 7 ms 4352 KB Output is correct
9 Correct 5 ms 4352 KB Output is correct
10 Correct 7 ms 4352 KB Output is correct
11 Correct 7 ms 4352 KB Output is correct
12 Correct 7 ms 4608 KB Output is correct
13 Correct 7 ms 4608 KB Output is correct
14 Correct 8 ms 4608 KB Output is correct
15 Correct 7 ms 4608 KB Output is correct
16 Correct 8 ms 4608 KB Output is correct
17 Correct 7 ms 4608 KB Output is correct
18 Correct 318 ms 23856 KB Output is correct
19 Correct 328 ms 28596 KB Output is correct
20 Correct 250 ms 27796 KB Output is correct
21 Correct 308 ms 28712 KB Output is correct
22 Correct 310 ms 28616 KB Output is correct
23 Correct 298 ms 28616 KB Output is correct
24 Correct 155 ms 28616 KB Output is correct