[link to the problem](https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cb14)↵
↵
↵
↵
~~~~~↵
Your code here...↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
↵
↵
#define pb push_back↵
#define ppb pop_back↵
#define pf push_front↵
#define ppf pop_front↵
#define all(x) (x).begin(),(x).end()↵
#define uniq(v) (v).erase(unique(all(v)),(v).end())↵
#define sz(x) (ll)((x).size())↵
#define pii pair<ll,ll>↵
#define piii pair<pair<ll,ll>,ll>↵
#define Piii pair<ll,pair<ll,ll>>↵
#define p_queue(a) priority_queue<a, vector<a>, greater<a>>↵
#define mp make_pair↵
#define se second↵
#define fi first↵
#define vi(a) vector<a>↵
#define vvi(a) vector <vector <a> >↵
#define pie 3.14159265358979323846↵
#define for0(i,a,b) for(ll i=a;i<b;i++)↵
#define for1(i,a,b) for(ll i=a;i<=b;i++)↵
#define mem1(a) memset(a,-1,sizeof(a))↵
#define mem0(a) memset(a,0,sizeof(a))↵
↵
//#define nsetbits(x) __builtin_popcountll(x)↵
↵
↵
//#include <ext/pb_ds/assoc_container.hpp> ↵
//#include <ext/pb_ds/tree_policy.hpp> ↵
//using namespace __gnu_pbds; ↵
// ↵
//template <typename num_t>↵
//using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;↵
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
//auto dist=uniform_int_distribution<int>(l,r);↵
↵
↵
typedef long long ll;↵
↵
const ll inf = 1000000007;↵
const ll mod = 1000000007;↵
const ll INF = 1e18 + 18;↵
↵
↵
vector<ll> dx={-1LL, 0LL, 1LL, 0LL}, dy={0LL, 1LL, 0LL, -1LL};↵
//vector<ll> dx={-1, -1, 0, 1, 1, 1, 0, -1}, dy={0, 1, 1, 1, 0, -1, -1, -1};↵
↵
↵
//string vowels = "aeiou";↵
//string consonants = "bcdfghjklmnpqrstvwxyz";↵
//string numbers = "0123456789";↵
//string alpha = "abcdefghijklmnopqrstuvwxyz";↵
↵
↵
bool check(ll i,ll j,ll r,ll c){↵
if(i >= 1 && i<= r && j >= 1 && j<= c){↵
return true;↵
}↵
return false;↵
}↵
↵
↵
↵
void test_case(){↵
↵
↵
ll r,c;↵
cin>>r>>c;↵
ll maxa = -1;↵
vector<vector<ll>> grid(r+2,vector<ll>(c+2));↵
// ll suma = 0;↵
for(ll i=1;i<=r;i++){↵
for(ll j=1;j<=c;j++){↵
cin>>grid[i][j];↵
maxa = max(maxa,grid[i][j]);↵
// suma += grid[i][j];↵
}↵
}↵
// priority_queue<Piii, vector<Piii>, greater<Piii>> q;↵
priority_queue<Piii> q;↵
vector<vector<bool>> vis(r+2,vector<bool>(c+2,false));↵
vector<vector<bool>> placed(r+2,vector<bool>(c+2,false));↵
for(ll i=1;i<=r;i++){↵
for(ll j=1;j<=c;j++){↵
if(grid[i][j] == maxa){↵
q.push(mp(maxa,mp(i,j)));↵
placed[i][j] = true;↵
// vis[i][j] = true;↵
}↵
}↵
}↵
ll ans = 0;↵
while(!q.empty()){↵
Piii node = q.top();↵
ll i = node.se.fi;↵
ll j = node.se.se;↵
ll w = node.fi;↵
q.pop();↵
for(ll k = 0;k<4;k++){↵
ll x = i + dx[k];↵
ll y = j + dy[k];↵
if(check(x,y,r,c) && !vis[x][y] && grid[x][y] < grid[i][j] && !placed[x][y]){↵
ll val = max(0LL,grid[i][j]-1-grid[x][y]);↵
grid[x][y] += val;↵
// vis[x][y] = true;↵
ans = 1LL*ans + val;↵
// if(placed[x][y]){↵
// continue;↵
// }↵
q.push(mp(grid[x][y],mp(x,y)));↵
placed[x][y] = true;↵
}↵
}↵
vis[i][j] = true;↵
}↵
// ll sumb = 0;↵
// for(ll i=1;i<=r;i++){↵
// for(ll j=1;j<=c;j++){↵
// cout<<grid[i][j]<<" ";↵
// sumb += grid[i][j];↵
// }↵
// cout<<endl;↵
// }↵
// cout<<"intial_sum = "<<suma<<" final_sum = "<<sumb<<endl;↵
cout<<ans<<endl;↵
↵
↵
↵
}↵
↵
↵
↵
void intialize(){↵
↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
}↵
↵
void preprocess(){↵
↵
↵
↵
}↵
↵
void codejam(ll t){↵
cout<<"Case #"<<t<<": ";↵
}↵
↵
int main(){↵
// clock_t start,end;↵
// start = clock();↵
intialize();↵
preprocess();↵
cout<<fixed<<setprecision(16);↵
// string a;↵
// getline(cin,a);↵
// test_case();↵
ll t;↵
cin>>t;↵
for(ll te=1;te<=t;te++){↵
codejam(te);↵
test_case();↵
}↵
// end = clock();↵
// double time_taken = double(end - start) / double(CLOCKS_PER_SEC);↵
// cout << "Time taken by program is : " << fixed << time_taken << setprecision(10);↵
// cout << " sec " << endl;↵
↵
↵
return 0;↵
}↵
↵
↵
↵
↵
↵
~~~~~↵
↵
↵
↵
↵
~~~~~↵
Your code here...↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
↵
↵
#define pb push_back↵
#define ppb pop_back↵
#define pf push_front↵
#define ppf pop_front↵
#define all(x) (x).begin(),(x).end()↵
#define uniq(v) (v).erase(unique(all(v)),(v).end())↵
#define sz(x) (ll)((x).size())↵
#define pii pair<ll,ll>↵
#define piii pair<pair<ll,ll>,ll>↵
#define Piii pair<ll,pair<ll,ll>>↵
#define p_queue(a) priority_queue<a, vector<a>, greater<a>>↵
#define mp make_pair↵
#define se second↵
#define fi first↵
#define vi(a) vector<a>↵
#define vvi(a) vector <vector <a> >↵
#define pie 3.14159265358979323846↵
#define for0(i,a,b) for(ll i=a;i<b;i++)↵
#define for1(i,a,b) for(ll i=a;i<=b;i++)↵
#define mem1(a) memset(a,-1,sizeof(a))↵
#define mem0(a) memset(a,0,sizeof(a))↵
↵
//#define nsetbits(x) __builtin_popcountll(x)↵
↵
↵
//#include <ext/pb_ds/assoc_container.hpp> ↵
//#include <ext/pb_ds/tree_policy.hpp> ↵
//using namespace __gnu_pbds; ↵
// ↵
//template <typename num_t>↵
//using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;↵
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
//auto dist=uniform_int_distribution<int>(l,r);↵
↵
↵
typedef long long ll;↵
↵
const ll inf = 1000000007;↵
const ll mod = 1000000007;↵
const ll INF = 1e18 + 18;↵
↵
↵
vector<ll> dx={-1LL, 0LL, 1LL, 0LL}, dy={0LL, 1LL, 0LL, -1LL};↵
//vector<ll> dx={-1, -1, 0, 1, 1, 1, 0, -1}, dy={0, 1, 1, 1, 0, -1, -1, -1};↵
↵
↵
//string vowels = "aeiou";↵
//string consonants = "bcdfghjklmnpqrstvwxyz";↵
//string numbers = "0123456789";↵
//string alpha = "abcdefghijklmnopqrstuvwxyz";↵
↵
↵
bool check(ll i,ll j,ll r,ll c){↵
if(i >= 1 && i<= r && j >= 1 && j<= c){↵
return true;↵
}↵
return false;↵
}↵
↵
↵
↵
void test_case(){↵
↵
↵
ll r,c;↵
cin>>r>>c;↵
ll maxa = -1;↵
vector<vector<ll>> grid(r+2,vector<ll>(c+2));↵
// ll suma = 0;↵
for(ll i=1;i<=r;i++){↵
for(ll j=1;j<=c;j++){↵
cin>>grid[i][j];↵
maxa = max(maxa,grid[i][j]);↵
// suma += grid[i][j];↵
}↵
}↵
// priority_queue<Piii, vector<Piii>, greater<Piii>> q;↵
priority_queue<Piii> q;↵
vector<vector<bool>> vis(r+2,vector<bool>(c+2,false));↵
vector<vector<bool>> placed(r+2,vector<bool>(c+2,false));↵
for(ll i=1;i<=r;i++){↵
for(ll j=1;j<=c;j++){↵
if(grid[i][j] == maxa){↵
q.push(mp(maxa,mp(i,j)));↵
placed[i][j] = true;↵
// vis[i][j] = true;↵
}↵
}↵
}↵
ll ans = 0;↵
while(!q.empty()){↵
Piii node = q.top();↵
ll i = node.se.fi;↵
ll j = node.se.se;↵
ll w = node.fi;↵
q.pop();↵
for(ll k = 0;k<4;k++){↵
ll x = i + dx[k];↵
ll y = j + dy[k];↵
if(check(x,y,r,c) && !vis[x][y] && grid[x][y] < grid[i][j] && !placed[x][y]){↵
ll val = max(0LL,grid[i][j]-1-grid[x][y]);↵
grid[x][y] += val;↵
// vis[x][y] = true;↵
ans = 1LL*ans + val;↵
// if(placed[x][y]){↵
// continue;↵
// }↵
q.push(mp(grid[x][y],mp(x,y)));↵
placed[x][y] = true;↵
}↵
}↵
vis[i][j] = true;↵
}↵
// ll sumb = 0;↵
// for(ll i=1;i<=r;i++){↵
// for(ll j=1;j<=c;j++){↵
// cout<<grid[i][j]<<" ";↵
// sumb += grid[i][j];↵
// }↵
// cout<<endl;↵
// }↵
// cout<<"intial_sum = "<<suma<<" final_sum = "<<sumb<<endl;↵
cout<<ans<<endl;↵
↵
↵
↵
}↵
↵
↵
↵
void intialize(){↵
↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
↵
}↵
↵
void preprocess(){↵
↵
↵
↵
}↵
↵
void codejam(ll t){↵
cout<<"Case #"<<t<<": ";↵
}↵
↵
int main(){↵
// clock_t start,end;↵
// start = clock();↵
intialize();↵
preprocess();↵
cout<<fixed<<setprecision(16);↵
// string a;↵
// getline(cin,a);↵
// test_case();↵
ll t;↵
cin>>t;↵
for(ll te=1;te<=t;te++){↵
codejam(te);↵
test_case();↵
}↵
// end = clock();↵
// double time_taken = double(end - start) / double(CLOCKS_PER_SEC);↵
// cout << "Time taken by program is : " << fixed << time_taken << setprecision(10);↵
// cout << " sec " << endl;↵
↵
↵
return 0;↵
}↵
↵
↵
↵
↵
↵
~~~~~↵
↵
