Submission #77835

#	Time	Username	Problem	Language	Result	Execution time	Memory
77835		Vardanyan	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1521 ms	253164 KiB

joioi

#include <bits/stdc++.h>
using namespace std;
const int N = 2007;
int a[N][N];
int n,m;
int mns = 1000*1000*1000;
bool rot(){
    vector<vector<int> > v;
    for(int i = 1;i<=n;i++){
        vector<int> u;
        for(int j = 1;j<=m;j++) u.push_back(a[i][j]);
        reverse(u.begin(),u.end());
        v.push_back(u);
    }
    for(int j = 1;j<=n;j++){
        for(int i = 0;i<v[j-1].size();i++){
            a[i+1][j] = v[j-1][i];
        }
    }
    swap(n,m);
}
bool check(int x){
    bool f = false;
    int ed = m;
    int mx = 0;
    int mn = 1000*1000*1000+5;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=ed;j++){
            if(a[i][j]-mns>x){
                ed = j-1;
                break;
            }
        }
        for(int j = ed+1;j<=m;j++){
            mx = max(mx,a[i][j]);
            mn = min(mn,a[i][j]);
        }
    }
    if(mx-mn<=x) f = true;
    return f;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++){
                scanf("%d",&a[i][j]);
                mns = min(mns,a[i][j]);
        }
    int mnans = 1000*1000*1000;
    for(int i = 0;i<4;i++){
    int l = 0;
    int r = 1000*1000*1000;
    int ans = r;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid)){
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    mnans = min(mnans,ans);
    rot();
    }
    cout<<mnans<<endl;
    return 0;
}

Compilation message (stderr)

joioi.cpp: In function 'bool rot()':
joioi.cpp:16:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<v[j-1].size();i++){
                       ~^~~~~~~~~~~~~~
joioi.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
joioi.cpp: In function 'int main()':
joioi.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
joioi.cpp:46:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&a[i][j]);
                 ~~~~~^~~~~~~~~~~~~~~

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