Submission #830933

#	Time	Username	Problem	Language	Result	Execution time	Memory
830933		YassineBenYounes	The Kingdom of JOIOI (JOI17_joioi)	C++17	60 / 100	465 ms	262144 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
typedef long long ll;
#define int ll
#define pii pair<int, int>
#define ff first
#define ss second
#define vii vector<pii>
#define pb push_back
#define vi vector<int>
const int mx = 2000;
const int inf = 1e15;
const int LOG = 22;

int n, m;

int grid[mx][mx];

int prefmin1[mx][mx];
int prefmin[mx][mx];
int prefmin2[mx][mx];
int prefmin3[mx][mx];

int prefmax1[mx][mx];
int prefmax[mx][mx];
int prefmax2[mx][mx];
int prefmax3[mx][mx];
vector<vi> v;

void preprocess(){
    for(int i = 0; i < n;i++){
        for(int j = 0;j < m;j++){
            int x = inf, y = inf;
            if(i > 0)x = prefmin[i-1][j];
            if(j > 0)y = prefmin[i][j-1];
            prefmin[i][j] = min(x, y);
            prefmin[i][j] = min(prefmin[i][j], grid[i][j]);
        }
    }
    for(int i = 0; i < n;i++){
        for(int j = 0;j < m;j++){
            int x = 0, y = 0;
            if(i > 0)x = prefmax[i-1][j];
            if(j > 0)y = prefmax[i][j-1];
            prefmax[i][j] = max(x, y);
            prefmax[i][j] = max(prefmax[i][j], grid[i][j]);
        }
    }
    // 1 : 
    for(int i = n-1; i >= 0;i--){
        for(int j = 0;j < m;j++){
            int x = inf, y = inf;
            if((i+1) < n)x = prefmin1[i+1][j];
            if(j > 0)y = prefmin1[i][j-1];
            prefmin1[i][j] = min(x, y);
            prefmin1[i][j] = min(prefmin1[i][j], grid[i][j]);
        }
    }
    for(int i = n-1; i >= 0;i--){
        for(int j = 0;j < m;j++){
            int x = 0, y = 0;
            if((i+1) < n)x = prefmax1[i+1][j];
            if(j > 0)y = prefmax1[i][j-1];
            prefmax1[i][j] = max(x, y);
            prefmax1[i][j] = max(prefmax1[i][j], grid[i][j]);
        }
    }
    // 2 : 
    for(int i = 0; i < n;i++){
        for(int j = m-1;j >= 0;j--){
            int x = inf, y = inf;
            if(i > 0)x = prefmin2[i-1][j];
            if((j+1) < m)y = prefmin2[i][j+1];
            prefmin2[i][j] = min(x, y);
            prefmin2[i][j] = min(prefmin2[i][j], grid[i][j]);
        }
    }
    for(int i = 0; i < n;i++){
        for(int j = m-1;j >= 0;j--){
            int x = 0, y = 0;
            if(i > 0)x = prefmax2[i-1][j];
            if((j+1) < m)y = prefmax2[i][j+1];
            prefmax2[i][j] = max(x, y);
            prefmax2[i][j] = max(prefmax2[i][j], grid[i][j]);
        }
    }
    // 3:
    for(int i = n-1; i >= 0;i--){
        for(int j = m-1;j >= 0;j--){
            int x = inf, y = inf;
            if((i+1) < n)x = prefmin3[i+1][j];
            if((j+1) < m)y = prefmin3[i][j+1];
            prefmin3[i][j] = min(x, y);
            prefmin3[i][j] = min(prefmin3[i][j], grid[i][j]);
        }
    }
    for(int i = n-1; i >= 0;i--){
        for(int j = m-1;j >= 0;j--){
            int x = 0, y = 0;
            if((i+1) < n)x = prefmax3[i+1][j];
            if((j+1) < m)y = prefmax3[i][j+1];
            prefmax3[i][j] = max(x, y);
            prefmax3[i][j] = max(prefmax3[i][j], grid[i][j]);
        }
    }
}

int32_t main(){
    cin.tie();cout.tie();ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 0; i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> grid[i][j];
            v.pb({grid[i][j], i, j});
        }
    }
    preprocess();
    int res = inf;
    sort(v.begin(), v.end());
    int a = inf, b = -inf;
    for(int i = 0; i < v.size();i++){
        if(i > 0){
            int x = v[i-1][1], y = v[i-1][2];
            a = min(a, prefmin[x][y]);
            b = max(b, prefmax[x][y]);
        }
        res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
    }
    a = inf, b = -inf;
    for(int i = 0; i < v.size();i++){
        if(i > 0){
            int x = v[i-1][1], y = v[i-1][2];
            a = min(a, prefmin1[x][y]);
            b = max(b, prefmax1[x][y]);
        }
        res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
    }
    a = inf, b = -inf;
    for(int i = 0; i < v.size();i++){
        if(i > 0){
            int x = v[i-1][1], y = v[i-1][2];
            a = min(a, prefmin2[x][y]);
            b = max(b, prefmax2[x][y]);
        }
        res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
    }
    a = inf, b = -inf;
    for(int i = 0; i < v.size();i++){
        if(i > 0){
            int x = v[i-1][1], y = v[i-1][2];
            a = min(a, prefmin3[x][y]);
            b = max(b, prefmax3[x][y]);
        }
        res = min(res, max(v[v.size()-1][0] - v[i][0], b-a));
    }
    cout << res << endl;
}

Compilation message (stderr)

joioi.cpp: In function 'int32_t main()':
joioi.cpp:130:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~
joioi.cpp:139:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~
joioi.cpp:148:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~
joioi.cpp:157:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for(int i = 0; i < v.size();i++){
      |                    ~~^~~~~~~~~~
joioi.cpp: In function 'void init()':
joioi.cpp:6:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
joioi.cpp:8:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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