Submission #1039075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039075		Andrey	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	922 ms	101984 KiB

joioi

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,pair<int,int>>> haha(0);
int bruh[2001][2001];
int n,m;

int calc() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            bruh[i][j] = 1;
        }
    }
    vector<int> sm(m);
    vector<int> big(m,-1);
    int ans = haha[haha.size()-1].first-haha[0].first;
    int br = 0,p = 0;
    for(int i = 0; i < n*m; i++) {
        int x = haha[i].second.first,y = haha[i].second.second;
        for(int j = y; j < m; j++) {
            if(big[j] >= sm[j]) {
                br--;
            }
            if(big[j] < x) {
                big[j] = x;
                if(big[j] >= sm[j]) {
                    br++;
                }
            }
            else {
                break;
            }
        }
        while(br > 0) {
            int a = haha[p].second.first,b = haha[p].second.second;
            bruh[a][b] = 0;
            if(big[b] >= sm[b]) {
                br--;
            }
            while(sm[b] < n && bruh[sm[b]][b] == 0) {
                sm[b]++;
            }
            if(big[b] >= sm[b]) {
                br++;
            }
            p++;
        }
        int c = haha[p-1].first-haha[0].first;
        if(i < n*m) {
            c = max(c,haha[n*m-1].first-haha[i+1].first);
        }
        ans = min(ans,c);
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    int a,ans = INT_MAX;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a;
            haha.push_back({a,{i,j}});
        }
    }
    sort(haha.begin(),haha.end());
    ans = min(ans,calc());
    for(int i = 0; i < n*m; i++) {
        haha[i] = {haha[i].first,{n-1-haha[i].second.first,m-1-haha[i].second.second}};
    }
    ans = min(ans,calc());
    for(int i = 0; i < n*m; i++) {
        haha[i] = {haha[i].first,{n-1-haha[i].second.first,haha[i].second.second}};
    }
    ans = min(ans,calc());
    for(int i = 0; i < n*m; i++) {
        haha[i] = {haha[i].first,{n-1-haha[i].second.first,m-1-haha[i].second.second}};
    }
    ans = min(ans,calc());
    cout << ans;
    return 0;
}

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