제출 #881970

#제출 시각아이디문제언어결과실행 시간메모리
881970noyancanturk최솟값 배열 (IZhO11_hyper)C++17
100 / 100
432 ms66132 KiB
#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1.5e6+100;
#else
    const int lim=3e3;
#endif

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

#define int long long
#define pb push_back

const int mod=1e9+7;
using pii=pair<int,int>;

void solve(){
    int n,m;
    cin>>n>>m;
    int nm=n-m+1;
    int a[n][n][n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                for(int l=0;l<n;l++){
                    cin>>a[i][j][k][l];
                }
            }
        }
    }
    int b[n][n][n][nm];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                multiset<int>sety;
                for(int l=0;l<m;l++){
                    sety.insert(a[i][j][k][l]);
                }
                b[i][j][k][0]=*sety.begin();
                for(int l=1;l<nm;l++){
                    sety.erase(sety.find(a[i][j][k][l-1]));
                    sety.insert(a[i][j][k][l+m-1]);
                    b[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int c[n][n][nm][nm];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int k=0;k<m;k++){
                    sety.insert(b[i][j][k][l]);
                }
                c[i][j][0][l]=*sety.begin();
                for(int k=1;k<nm;k++){
                    sety.erase(sety.find(b[i][j][k-1][l]));
                    sety.insert(b[i][j][k+m-1][l]);
                    c[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int d[n][nm][nm][nm];
    for(int i=0;i<n;i++){
        for(int k=0;k<nm;k++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int j=0;j<m;j++){
                    sety.insert(c[i][j][k][l]);
                }
                d[i][0][k][l]=*sety.begin();
                for(int j=1;j<nm;j++){
                    sety.erase(sety.find(c[i][j-1][k][l]));
                    sety.insert(c[i][j+m-1][k][l]);
                    d[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    int ans[nm][nm][nm][nm];
    for(int j=0;j<nm;j++){
        for(int k=0;k<nm;k++){
            for(int l=0;l<nm;l++){
                multiset<int>sety;
                for(int i=0;i<m;i++){
                    sety.insert(d[i][j][k][l]);
                }
                ans[0][j][k][l]=*sety.begin();
                for(int i=1;i<nm;i++){
                    sety.erase(sety.find(d[i-1][j][k][l]));
                    sety.insert(d[i+m-1][j][k][l]);
                    ans[i][j][k][l]=*sety.begin();
                }
            }
        }
    }
    for(int i=0;i<nm;i++){
        for(int j=0;j<nm;j++){
            for(int k=0;k<nm;k++){
                for(int l=0;l<nm;l++){
                    cout<<ans[i][j][k][l]<<" ";
                }
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...