Submission #1005667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005667		dimashhh	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	4041 ms	58504 KiB

joioi

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int  N = 2e3 + 2, MOD = (int)1e9 + 7;

int n,m,a[N][N],b[N][N];
void rot(){
    // for(int i = 1;i <= n;i++){
    //     for(int j = 1;j <= m;j++){
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            a[m - j + 1][i] = b[i][j];
        }
    }
    swap(n,m);
    // cout << "rot\n";
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            b[i][j] = a[i][j];
            // cout << a[i][j] << ' ';
        }
        // cout << '\n';
    }
    // cout << '\n';
}
int mn = 1e9;
int it[N];
bool check(int mid){
    int l = mn,r = l + mid;
    it[0] = m;
    for(int i = 1;i <= n;i++){
        it[i] = 0;
        for(int j = 1;j <= it[i - 1] && a[i][j] >= l && a[i][j] <= r;j++){
            it[i] = j;
        }
    }
    set<int> st;
    for(int i = 1;i <= n;i++){
        for(int j = it[i] + 1;j <= m;j++){
            st.insert(a[i][j]);
        }
    }
    return (st.empty() || (*st.rbegin() - *st.begin() <= mid));
}
bool ok(int mid){
    bool res = false;
    for(int i = 0;i < 4;i++){
        if(check(mid)){
            res = 1;
        }
        rot();
    }
    return res;
}
void test(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;++j){
            cin >> a[i][j];
            b[i][j] = a[i][j];
            mn = min(mn,a[i][j]);
        }
    }
    int l = -1,r = 1e9 + 1;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(ok(mid)){
            r = mid;
        }else{
            l = mid;
        }
        // cout << mid << ' ' << ok(mid) << ' ' << check(mid) << '\n';
    }
    cout << r << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        test();
    }
}

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