Submission #210936

#TimeUsernameProblemLanguageResultExecution timeMemory
210936ryanseeMaxcomp (info1cup18_maxcomp)C++14
100 / 100
328 ms28712 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...