pms_venkatesh_saki_147's blog

By pms_venkatesh_saki_147, history, 4 years ago, In English

link to the problem

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;
}





Full text and comments »