fork download
copy 
  1. #include <math.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef unsigned long long ull;
  7. using ul = uint64_t;
  8. using db = long double;
  9. void Code_By_Mohamed_Khaled(){
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12. #ifndef ONLINE_JUDGE
  13.     freopen("input.txt", "r", stdin);
  14.     freopen("output.txt", "w", stdout);
  15. #endif
  16. }
  17. const ll mod=1e9+7;
  18. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  19. inline ll mul(ll a, ll b) {a%=mod;b%=mod;ll x=a*b;return x>=mod ? x%mod:x;}
  20. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
  21. int main(){
  22.     Code_By_Mohamed_Khaled();
  23.     ll t;cin>>t;
  24.     while (t--) {
  25.         ll n,m;cin>>n>>m;
  26.         vector<vector<ll>>v(n,vector<ll>(m));
  27.         for (ll i=0; i<n; i++) {
  28.             for (ll j=0;j<m;j++) {
  29.                 cin>>v[i][j];
  30.             }
  31.         }
  32.         if(n == 1 || m == 1) {
  33.             ll mx=LLONG_MIN;
  34.             for (auto it:v) {
  35.                 for (auto i:it)mx=max(mx,i);
  36.             }
  37.             cout<<mx-1<<"\n";
  38.             continue;
  39.         }
  40.         vector<ll>row(n,0),row_max_col(n,0),second_row_max(n, 0);
  41.         for (int i=0;i<n;i++){
  42.             ll first=-1,second=-1,idx=-1;
  43.             for (int j=0;j<m;j++){
  44.                 ll val=v[i][j];
  45.                 if(val>first){
  46.                     second=first;
  47.                     first=val;
  48.                     idx=j;
  49.                 }
  50.                 else if(val>second){
  51.                     second=val;
  52.                 }
  53.             }
  54.             row[i]=first;
  55.             row_max_col[i]=idx;
  56.             second_row_max[i]=second;
  57.         }
  58.         vector<ll>col(m, 0);
  59.         for (int j=0;j<m;j++){
  60.             ll maxi=0;
  61.             for (int i=0;i<n; i++){
  62.                 maxi=max(maxi, v[i][j]);
  63.             }
  64.             col[j]=maxi;
  65.         }
  66.         vector<vector<ll>>temp(m,vector<ll>(n,0));
  67.         vector<vector<ll>>left_max(m,vector<ll>(n,0)),right_max(m,vector<ll>(n,0));
  68.         for (int c = 0; c < m; c++){
  69.             for (int i = 0; i < n; i++){
  70.                 if(row_max_col[i]==c)temp[c][i]=second_row_max[i];
  71.                 else temp[c][i]=row[i];
  72.             }
  73.             left_max[c][0]=temp[c][0];
  74.             for (int i=1;i<n;i++){
  75.                 left_max[c][i]=max(left_max[c][i-1],temp[c][i]);
  76.             }
  77.             right_max[c][n-1]=temp[c][n-1];
  78.             for (int i=n-2;i>=0;i--){
  79.                 right_max[c][i]=max(right_max[c][i+1],temp[c][i]);
  80.             }
  81.         }
  82.         ll ans=LLONG_MAX;
  83.         for (ll r=0;r<n;r++){
  84.             ll o=row[r]-1;
  85.             for (int c = 0; c < m; c++){
  86.                 ll x=col[c]-1;
  87.                 ll a;
  88.                 if(r==0) a=right_max[c][1];
  89.                 else if(r==n-1)a=left_max[c][n - 2];
  90.                 else a=max(left_max[c][r-1],right_max[c][r+1]);
  91.                 ll cur=max({o,x,a});
  92.                 ans=min(ans, cur);
  93.             }
  94.         }
  95.         cout<<ans<<"\n";
  96.     }
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
1 1
1
1 2
1 2
2 1
2
1
2 2
4 2
3 4
3 4
1 2 3 2
3 2 1 3
2 1 3 2
4 3
1 5 1
3 1 3
5 5 5
3 5 1
4 4
1 3 3 2
2 3 2 2
1 2 2 1
3 3 2 3
2 2
2 2
1 2
3 2
1 2
2 1
1 2
3 3
2 1 1
1 2 1
1 1 2
stdout
copy 
0
1
1
3
2
4
3
1
1
2
https://ideone.com/jpwbN0
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!