답안 #38668

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38668	2018-01-05T19:08:29 Z	alenam0161	최솟값 배열 (IZhO11_hyper)	C++14	100 / 100	583 ms	38628 KB

hyper

#include <bits/stdc++.h>

using namespace std;
const int N  = 37;

struct sptable{
    deque<pair<int,int>> q;
    void clear(){
        q.clear();
    }
    void push(int x){
        int qan = 1;
        while(!q.empty()&&q.back().first>x){
            qan+=q.back().second;q.pop_back();
        }
        q.push_back({x,qan});
    }
    void remove(){
        q.front().second--;
        while(!q.empty()&&q.front().second==0)q.pop_front();
    }
    int m(){
        if(q.empty())return 0;
        return q.front().first;
    }
}cur;

int a[N][N][N][N];
int dp1[N][N][N][N];
int dp2[N][N][N][N];
int dp3[N][N][N][N];
int dp4[N][N][N][N];
int main(){

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                for(int l=1;l<=n;++l)
                    scanf("%d",&a[i][j][k][l]);
    //  i
    for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int i=1;i<m;++i){
                    cur.push(a[i][j][k][l]);
                }
                for(int i=m;i<=n;++i){
                    cur.push(a[i][j][k][l]);
                    dp1[i-m+1][j][k][l]=cur.m();
                    cur.remove();
                }
            }
    // j
    for(int i=1;i<=n-m+1;i++)
        for(int k=1;k<=n;++k)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int j=1;j<m;++j){
                    cur.push(dp1[i][j][k][l]);
                }
                for(int j=m;j<=n;++j){
                    cur.push(dp1[i][j][k][l]);
                    dp2[i][j-m+1][k][l]=cur.m();
                    cur.remove();
                }
            }
    // k
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int l=1;l<=n;++l){
                cur.clear();
                for(int k=1;k<m;++k){
                    cur.push(dp2[i][j][k][l]);
                }
                for(int k=m;k<=n;++k){
                    cur.push(dp2[i][j][k][l]);
                    dp3[i][j][k-m+1][l]=cur.m();
                    cur.remove();
                }
            }
    // l
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k){
                cur.clear();
                for(int l=1;l<m;++l){
                    cur.push(dp3[i][j][k][l]);
                }
                for(int l=m;l<=n;++l){
                    cur.push(dp3[i][j][k][l]);
                    dp4[i][j][k][l-m+1]=cur.m();
                    cur.remove();
                }
            }
    for(int i=1;i<=n-m+1;++i)
        for(int j=1;j<=n-m+1;++j)
            for(int k=1;k<=n-m+1;++k)
                for(int l=1;l<=n-m+1;++l){
                    printf("%d ",dp4[i][j][k][l]);
                }
    return 0;
}

Compilation message

hyper.cpp: In function 'int main()':
hyper.cpp:36:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
hyper.cpp:41:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                     scanf("%d",&a[i][j][k][l]);
                                               ^

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	38628 KB	Output is correct
2	Correct	0 ms	38628 KB	Output is correct
3	Correct	3 ms	38628 KB	Output is correct
4	Correct	0 ms	38628 KB	Output is correct
5	Correct	6 ms	38628 KB	Output is correct
6	Correct	16 ms	38628 KB	Output is correct
7	Correct	13 ms	38628 KB	Output is correct
8	Correct	39 ms	38628 KB	Output is correct
9	Correct	66 ms	38628 KB	Output is correct
10	Correct	39 ms	38628 KB	Output is correct
11	Correct	133 ms	38628 KB	Output is correct
12	Correct	269 ms	38628 KB	Output is correct
13	Correct	186 ms	38628 KB	Output is correct
14	Correct	296 ms	38628 KB	Output is correct
15	Correct	459 ms	38628 KB	Output is correct
16	Correct	326 ms	38628 KB	Output is correct
17	Correct	339 ms	38628 KB	Output is correct
18	Correct	583 ms	38628 KB	Output is correct
19	Correct	469 ms	38628 KB	Output is correct
20	Correct	363 ms	38628 KB	Output is correct