oj.uz

Submission #1023135

# Submission time Handle Problem Language Result Execution time Memory
1023135 2024-07-14T10:35:41 Z vjudge1 The Kingdom of JOIOI (JOI17_joioi) C++17
15 / 100
 4000 ms 2252 KB 
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define ROF(i,m,n) for(int i=m;i<=n;i++)
#define vi vector<int>
#define pb push_back
#define alle(a) a.begin(),a.end()
#define rall(n) rbegin(n),rend(n)
#define int long long
#define vecs vector<int> 
#define ll long long
#define ss second 
#define ff first
const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;



void solve(){
    int n , m;
    cin>>n>>m;
    vector <vector<int>> a(n,vector <int> (m));
    int mx = 0;
    int mn = INF;
    int ans = 0;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin>>a[i][j];
            mx = max(mx,a[i][j]);
            mn = min(mn,a[i][j]);

        }
    }
    auto check = [&](int m1){
        vector <vector<int>> color1(n,vector<int> (m));
        vector <vector<int>> color2(n,vector<int> (m));
        vector <vector<int>> color3(n,vector<int> (m));
        vector <vector<int>> color4(n,vector<int> (m));
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(abs(a[i][j] - mx) <= m1){
                    if(abs(a[i][j] - mn) <= m1){
                        color1[i][j] = 3;
                        color2[i][j] = 3;
                        color3[i][j] = 3;
                        color4[i][j] = 3;
                    }
                    else{
                        color1[i][j] = 1;
                        color2[i][j] = 1;
                        color3[i][j] = 1;
                        color4[i][j] = 1;
                    }
                    
                }
                else if(abs(a[i][j] - mn) <= m1){
                    color1[i][j] = 2;
                    color2[i][j] = 2;
                    color3[i][j] = 2;
                    color4[i][j] = 2;
                }
                else{
                    return false;
                }
            }
        }

        if(color1[0][0] == 1||color1[0][0] == 3){
            for(int i =0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color1[i][j] == 1){
                        for(int q = i;q >= 0;q--){
                            for(int p = j;p >= 0;p--){
                                color1[q][p] = 1;
                            }
                        }

                    }
                }
            }
            int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color1[i][j] == 3){
                        color1[i][j] = 2;
                    }
                    if(color1[i][j] == 1){
                        mx1 = max(mx1,a[i][j]);
                        mn1 = min(mn1,a[i][j]);
                    }
                    else if(color1[i][j] == 2){
                        mx2 = max(mx2,a[i][j]);
                        mn2 = min(mn2,a[i][j]);
                    }
                }
            }
            if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
                return true;
            }
        }
        if(color2[0][m - 1] == 1||color2[0][m - 1] == 3){
            for(int i =0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color2[i][j] == 1){
                        for(int q = i;q >= 0;q--){
                            for(int p = j;p < m;p++){
                                color2[q][p] = 1;
                            }
                        }
                    }
                }
            }
            int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color2[i][j] == 3){
                        color2[i][j] = 2;
                    }
                    if(color2[i][j] == 1){
                        mx1 = max(mx1,a[i][j]);
                        mn1 = min(mn1,a[i][j]);
                    }
                    else if(color2[i][j] == 2){
                        mx2 = max(mx2,a[i][j]);
                        mn2 = min(mn2,a[i][j]);
                    }
                }
            }
            if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
                return true;
            }
        }
        if(color3[n - 1][0] == 1||color3[n - 1][0] == 3){
            for(int i =0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color3[i][j] == 1){
                        for(int q = i;q < n;q++){
                            for(int p = j;p >= 0;p--){
                                color3[q][p] = 1;
                            }
                        }
                    }
                }
            }
            int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color3[i][j] == 3){
                        color3[i][j] = 2;
                    }
                    if(color3[i][j] == 1){
                        mx1 = max(mx1,a[i][j]);
                        mn1 = min(mn1,a[i][j]);
                    }
                    else if(color3[i][j] == 2){
                        mx2 = max(mx2,a[i][j]);
                        mn2 = min(mn2,a[i][j]);
                    }
                }
            }
            if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
                return true;
            }
        }
        if(color4[n - 1][m - 1] == 1||color4[n - 1][m - 1] == 3){
            for(int i =0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color4[i][j] == 1){
                        for(int q = i;q < n;q++){
                            for(int p = j;p < m;p++){
                                color4[q][p] = 1;
                            }
                        }
                    }
                }
            }
            int mx1 = 0, mn1 =INF, mx2 = 0,mn2 = INF;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < m;j++){
                    if(color4[i][j] == 3){
                        color4[i][j] = 2;
                    }
                    if(color4[i][j] == 1){
                        mx1 = max(mx1,a[i][j]);
                        mn1 = min(mn1,a[i][j]);
                    }
                    else if(color4[i][j] == 2){
                        mx2 = max(mx2,a[i][j]);
                        mn2 = min(mn2,a[i][j]);
                    }
                }
            }
            if((mx1 - mn1 <= m1) && (mx2 - mn2 <= m1)){
                return true;
            }
        }
        return false;
    };
    int l = 0,r = mx - mn;
    while(1 < r - l){
        int m2 = (l + r) >> 1;
        if(check(m2)){
            r = m2;
        }
        else{
            l = m2;
        }
    }
    if(check(l)){
        cout<<l;
    }
    else{
        cout<<r;
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

Compilation message

joioi.cpp: In function 'void solve()':
joioi.cpp:28:9: warning: unused variable 'ans' [-Wunused-variable]
   28 |     int ans = 0;
      |         ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 12 ms 348 KB Output is correct
16 Correct 2506 ms 1968 KB Output is correct
17 Execution timed out 4005 ms 2252 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 12 ms 348 KB Output is correct
16 Correct 2506 ms 1968 KB Output is correct
17 Execution timed out 4005 ms 2252 KB Time limit exceeded
18 Halted 0 ms 0 KB -