Submission #416257

#	Time	Username	Problem	Language	Result	Execution time	Memory
416257		Vladth11	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2713 ms	117544 KiB

joioi

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
//#include"holiday.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 2001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 666013;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;

int dp[NMAX][NMAX][2];
int sus[NMAX][NMAX];
int jos[NMAX][NMAX];
int mat[NMAX][NMAX];
int joi[NMAX]; /// asta e ala cu minimul
int ioi[NMAX]; /// asta e ala cu maximul
int fjoi[NMAX]; /// asta e ala cu minimul
int fioi[NMAX]; /// asta e ala cu maximul
int maxim = 0;
int minim = 2e9;
int n, m;

bool sePoate(){
     for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            dp[i][j][0] = dp[i][j][1] = 0;
            jos[i][j] = sus[i][j] = 0;
        }
    }
    for(int i = 0; i <= m; i++)
        jos[0][i] = sus[0][i] = 1;
    int ok = 1;
    for(int i = 1; i <= n; i++){
        for(int j = joi[i]; j < fioi[i]; j++){
            dp[i][j][0] |= jos[i - 1][j];
            dp[i][j][1] |= sus[i - 1][j];
        }
        jos[i][0] = dp[i][0][0];
        for(int j = 1; j <= m; j++){
            jos[i][j] = (jos[i][j - 1] | dp[i][j][0]);
        }
        sus[i][m] = dp[i][m][1];
        for(int j = m - 1; j >= 0; j--){
            sus[i][j] = (sus[i][j + 1] | dp[i][j][1]);
        }
    }
    return (jos[n][m] | sus[n][0]);
}

bool OK(int dif){
    if(maxim - minim <= dif)
        return 1;
    for(int j = 1; j <= n; j++){
        ioi[j] = joi[j] = 0;
        fioi[j] = fjoi[j] = m + 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(minim + dif < mat[i][j] && maxim - dif > mat[i][j])
                return 0;
            if(minim + dif >= mat[i][j] && maxim - dif > mat[i][j]){
                joi[i] = j;
                if(fjoi[i] == m + 1)
                    fjoi[i] = j;
            }
            else if(minim + dif < mat[i][j] && maxim - dif <= mat[i][j]){
                ioi[i] = j;
                if(fioi[i] == m + 1)
                    fioi[i] = j;
            }
        }
    }
    int ok = sePoate();
    for(int i = 1; i <= n; i++){
        swap(ioi[i], joi[i]);
        swap(fioi[i], fjoi[i]);
    }
    ok |= sePoate();
    return ok;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i, j;
    cin >> n >> m;
    for(i = 1; i <= n; i++){
        for(j = 1; j <= m; j++){
            cin >> mat[i][j];
            maxim = max(maxim, mat[i][j]);
            minim = min(minim, mat[i][j]);
        }
    }
    int r = 0, pas = (1 << 30);
   while(pas){
        if(!OK(r + pas))
            r += pas;
        pas /= 2;
    }
    if(!OK(r))
        r++;
    cout << r;
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'bool sePoate()':
joioi.cpp:44:9: warning: unused variable 'ok' [-Wunused-variable]
   44 |     int ok = 1;
      |         ^~

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