제출 #1316152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316152		abcd123456	The Kingdom of JOIOI (JOI17_joioi)	C++20	100 / 100	944 ms	63208 KiB

joioi

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define maxn 2005
#define fi first
#define se second
#define sti string
using namespace std;

ll a[maxn][maxn],b[maxn][maxn];
ll H,W,Min=4e18,Max=-4e18;

bool check(int Diff){
   int firstI=0;
   for(int i=1;i<=H;i++){
     for(int j=1;j<=W;j++){
        if(b[i][j] < Max-Diff){
            firstI=max(firstI,j);
        }
     }
     for(int j=1;j<=W;j++){
        if(b[i][j] > Min+Diff){
            if(j<=firstI) return 0;
        }
     }
   }
   return 1;
}

void flip_none() {
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            b[i][j] = a[i][j];
}

void flip_vertical() {
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            b[i][j] = a[H - i + 1][j];
}

void flip_horizontal() {
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            b[i][j] = a[i][W - j + 1];
}

void flip_both() {
    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= W; j++)
            b[i][j] = a[H - i + 1][W - j + 1];
}

bool ok(int D) {
    flip_none();
    if (check(D)) return 1;
    flip_vertical();
    if (check(D)) return 1;
    flip_horizontal();
    if (check(D)) return 1;
    flip_both();
    if (check(D)) return 1;
    return 0;
}

signed main ()
{
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   cin>>H>>W;
   for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
         cin>>a[i][j];
         Min=min(Min,a[i][j]);
         Max=max(Max,a[i][j]);
    }
   }
   ll L=0,R=Max-Min,ans=R;
   while(L<=R){
      ll mid=(L+R)/2;
      if(ok(mid)){
        ans=mid;
        R=mid-1;
      }
      else L=mid+1;
   }
   cout<<ans;
   return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40