oj.uz

Submission #332870

# Submission time Handle Problem Language Result Execution time Memory
332870 2020-12-03T22:29:39 Z limabeans The Kingdom of JOIOI (JOI17_joioi) C++17
0 / 100
 4000 ms 492 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll inf = 1e18;
const int maxn = 2020;


int n,m;
ll g[maxn][maxn];
ll tmp[maxn][maxn];


int mark[maxn][maxn];

bool test(ll diff) {
    ll mn = inf;
    ll mx = -inf;
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    mn = min(mn, g[i][j]);
	    mx = max(mx, g[i][j]);
	}
    }

    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    mark[i][j] = -1;
	}
    }

    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    if (mark[i][j]==-1) {
		if (g[i][j]<mx-diff) {
		    mark[i][j]=0;
		} else if (mn+diff<g[i][j]) {
		    mark[i][j]=1;
		}
	    }
	}
    }

    int right0 = m-1;

    for (int i=0; i<n; i++) {
	int r0 = 0;
	int l1 = m;
	for (int j=0; j<m; j++) {
	    if (mark[i][j]==0) {
		r0=j;
	    } else if (mark[i][j]==1) {
		l1=min(l1,j);
	    }
	}
	if (r0>l1) return false;
	if (r0>right0) return false;
	right0 = min(right0, l1-1);
	//watch(right0);
    }

    return true;
}

ll solve() {
    ll mn = inf;
    ll mx = -inf;
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    mn = min(mn, g[i][j]);
	    mx = max(mx, g[i][j]);
	}
    }

    for (ll i=0; i<=mx-mn; i++) {
	if (test(i)) return i;
    }

    assert(false);
    return -1;
}


void flipY() {
    for (int i=0; i<n; i++) {
	for (int j=0; j<m/2; j++) {
	    swap(g[i][j],g[i][m-j-1]);
	}
    }
}

void transpose() {
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    tmp[j][i]=g[i][j];
	}
    }
    swap(n,m);
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    g[i][j]=tmp[i][j];
	}
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);


    cin>>n>>m;
    for (int i=0; i<n; i++) {
	for (int j=0; j<m; j++) {
	    cin>>g[i][j];
	}
    }

    ll res = inf;
    res = min(res, solve());
    flipY();
    res = min(res, solve());
    flipY(); transpose();
    res = min(res, solve());
    flipY();
    res = min(res, solve());

    cout<<res<<endl;
    
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Execution timed out 4073 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Execution timed out 4073 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Execution timed out 4073 ms 364 KB Time limit exceeded
4 Halted 0 ms 0 KB -