제출 #1199586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199586		hyl_backup	The Kingdom of JOIOI (JOI17_joioi)	C++20	0 / 100	86 ms	189708 KiB

joioi

//The Kingdom of JOIOI
#include <iostream>
#include <set>
#include <climits>
#include <vector>

#define MIN(a, b) ((a<b)? a :b )
#define MAX(a, b) ((a>b)? a :b )

long long h, w, min, max, col, a, b, min_a, min_b, max_a, max_b;
long long limit, ans;

long long mat[2007][2007];
int loga[2007] = {};
int binexp[12] = {};

std::set<std::pair<long long, long long>> set;

void b_log(){
    long long bin=2;
    int cont = 1;
    for(int i = 1; i<2005; ++i){
        if(i>=bin){
            bin*=2;
            ++cont;
        }
        loga[i]=cont;
        //std::cout << loga[i] <<'\n';
    }
    bin = 1;
    for(int i = 0; i<11; ++i){

    }
}

struct sparse{
    std::vector<int> min;
    std::vector<int> max;
};

sparse table[2007][2007];

void b_sparse(){
    for(int i = h-1; i>=0; --i){
        table[col][i].min.push_back(mat[i][col]);
        table[col][i].max.push_back(mat[i][col]);
        for(int j = 1; j+i<h; j*=2){
            //std::cout << '-'<< i+j-j/2 <<' '<<j/2 <<':'<<loga[j/2]<< '_';
            table[col][i].min.push_back(MIN(table[col][i].min[loga[j/2]], table[col][i+j-j/2].min[loga[j/2]]));
            table[col][i].max.push_back(MAX(table[col][i].max[loga[j/2]], table[col][i+j-j/2].max[loga[j/2]]));
        }
        /*
        for(int x : table[col][i].min){
            std::cout << x <<' ';
        }
        std::cout << '\n';
        for(int x : table[col][i].max){
            std::cout << x <<' ';
        }
        std::cout << '\n';
        */
    }
}

int min_tree(){
    int range=b-a;
    return MIN(table[col][a].min[loga[range]], table[col][b-(range/2)*2].min[loga[range]]);
}
int max_tree(){
    int range=b-a;
    return MAX(table[col][a].max[loga[range]], table[col][b-(range/2)*2].max[loga[range]]);
}


std::set<std::vector<int>> dp;
std::set<std::vector<int>> dp2;

int main(){
    //std::cin.tie(0);
    //std::ios_base::sync_with_stdio(0);

    b_log();

    std::cin >> h >> w;

    for(int i = 0; i<h; ++i){
        for(int j = 0; j<w; ++j){
            std::cin >> mat[i][j];
            //og.insert(mat[i][j]);
        }
    }

    min = LLONG_MAX;

    for(int j = 0; j<w; ++j){
        col=j;
        b_sparse();
    }

    col = 0;

    a = 0;
    b = 3;
    //std::cout << min_tree() << ' ' << max_tree()<<'\n';

    //return 0;

    ans = LLONG_MAX;

    //ms_b=og;

    dp.insert({h-1, 2000123000, 0, 2000123000, 0});


    for(int j = 0; j<=w; ++j){
        for(std::vector<int> x : dp){
            //limit, min, max, min, max
            /*
            std::cout << j<<"pos ";
            for(int c : x){
                std::cout << c <<' ';
            }
            std::cout <<'\n';
            //*/

            limit=x[0];

            if(j==w){
                ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
                continue;
            }

            col= j;
            a=0;
            b=h-1;
            dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

            min=x[1];
            max=x[2];

            for(int i = 0; i<=limit; ++i){
                min = MIN(min, mat[i][j]);
                max = MAX(max, mat[i][j]);


                a=i+1;

                if(a<h){
                    dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
                }
                else{
                    dp2.insert({i, min, max, x[3], x[4]});
                }
            }

        }
        dp.clear();
        dp=dp2;
        dp2.clear();
    }

    //return 0 ;
    //std::cout << "prelim: " << ans <<'\n';

    dp.clear();

    dp.insert({-1, 2000123000, 0, 2000123000, 0});

    for(int j = 0; j<=w; ++j){
        for(std::vector<int> x : dp){
            //limit, min, max, min, max
            /*
            std::cout << j<<"pos ";
            for(int c : x){
                std::cout << c <<' ';
            }
            std::cout <<'\n';
            //*/

            limit=x[0];

            if(j==w){
                ans = MIN(ans, MAX(x[2]-x[1], x[4]-x[3]));
                continue;
            }

            col= j;
            a=0;
            b=h-1;
            //dp2.insert({-1, x[1], x[2], MIN(x[3], min_tree()), MAX(x[4], max_tree())});

            min=x[1];
            max=x[2];

            for(int i = 0; i<limit; ++i){
                min = MIN(min, mat[i][j]);
                max = MAX(max, mat[i][j]);
            }

            for(int i = limit; i<h; ++i){
                if(i>=0){
                    min = MIN(min, mat[i][j]);
                    max = MAX(max, mat[i][j]);
                }

                //std::cout <<min <<':' << max <<'\n';

                a=i+1;
                if(a<h){
                    dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
                }
                else{
                    dp2.insert({i, min, max, x[3], x[4]});
                }
            }

        }
        dp.clear();
        dp=dp2;
        dp2.clear();
    }

    std::cout << ans;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joioi.cpp: In function 'int main()':
joioi.cpp:112:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]
  112 |     dp.insert({h-1, 2000123000, 0, 2000123000, 0});
      |                ~^~
joioi.cpp:112:17: warning: narrowing conversion of '(h - 1)' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:149:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  149 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                    ^~~
joioi.cpp:149:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:149:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  149 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                         ^~~
joioi.cpp:149:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:152:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  152 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                    ^~~
joioi.cpp:152:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:152:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  152 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                         ^~~
joioi.cpp:152:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:210:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  210 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                    ^~~
joioi.cpp:210:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:210:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  210 |                     dp2.insert({i, min, max, MIN(x[3], min_tree()), MAX(x[4], max_tree())});
      |                                         ^~~
joioi.cpp:210:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:213:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
  213 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                    ^~~
joioi.cpp:213:36: warning: narrowing conversion of 'min' from 'long long int' to 'int' [-Wnarrowing]
joioi.cpp:213:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]
  213 |                     dp2.insert({i, min, max, x[3], x[4]});
      |                                         ^~~
joioi.cpp:213:41: warning: narrowing conversion of 'max' from 'long long int' to 'int' [-Wnarrowing]

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