Submission #847779

#	Time	Username	Problem	Language	Result	Execution time	Memory
847779		Essa2006	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1711 ms	56872 KiB

joioi

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n, m;
    cin>>n>>m;
    vector<vector<int>>A(n, vector<int>(m));
    int mn=1e9, mx=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>A[i][j];
            mn=min(mn, A[i][j]);
            mx=max(mx, A[i][j]);
        }
    }
    int l=0, r=1e9, ans;
    while(l<=r){
        int md=(l+r)/2;
        vector<vector<bool>>B(n, vector<bool>(m));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mx-A[i][j]>md)
                    B[i][j]=1;
            }
        }
        bool can=0, cur;
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=0;i<n;i++){
                for(int j=m-1;j>=0;j--){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i!=n-1){
                            B2[i+1][j]=1;
                        }
                        if(j){
                            B2[i][j-1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i!=n-1){
                            B2[i+1][j]=1;
                        }
                        if(j!=m-1){
                            B2[i][j+1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=n-1;i>=0;i--){
                for(int j=m-1;j>=0;j--){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i){
                            B2[i-1][j]=1;
                        }
                        if(j){
                            B2[i][j-1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        {
            cur=1;
            vector<vector<bool>>B2=B;
            for(int i=n-1;i>=0;i--){
                for(int j=0;j<m;j++){
                    if(B2[i][j]){
                        if(A[i][j]-mn>md)
                            cur=0;
                        if(i){
                            B2[i-1][j]=1;
                        }
                        if(j!=m-1){
                            B2[i][j+1]=1;
                        }
                    }
                }
            }
            can|=cur;
        }
        if(can)
            ans=md, r=md-1;
        else
            l=md+1;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

joioi.cpp: In function 'int main()':
joioi.cpp:4:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define endl '\n'
      |              ^~~~
joioi.cpp:22:21: note: 'ans' was declared here
   22 |     int l=0, r=1e9, ans;
      |                     ^~~

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