제출 #992140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992140		irmuun	The Kingdom of JOIOI (JOI17_joioi)	C++17	100 / 100	2577 ms	102344 KiB

joioi

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll H,W;
ll a[2005][2005],b[2005][2005];

void rotate(){
    for(ll i=1;i<=H;i++){
        for(ll j=1;j<=W;j++){
            b[i][j]=a[i][j];
        }
    }
    for(ll j=1;j<=W;j++){
        for(ll i=H;i>=1;i--){
            a[j][H+1-i]=b[i][j];
        }
    }
    swap(H,W);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>H>>W;
    for(ll i=1;i<=H;i++){
        for(ll j=1;j<=W;j++){
            cin>>a[i][j];
        }
    }
    ll row[2005];
    ll l=0,r=1e9;
    while(l<r){
        ll mid=(l+r)/2;//check
        bool ok=false;
        for(ll z=0;z<4;z++){
            rotate();
            ll val=1e9+5,x,y;
            for(ll i=1;i<=H;i++){
                for(ll j=1;j<=W;j++){
                    if(a[i][j]<val){
                        val=a[i][j];
                        x=i;
                        y=j;
                    }
                }
            }
            for(ll i=1;i<=H;i++){
                row[i]=0;
                for(ll j=1;j<=W;j++){
                    if(a[i][j]<=val+mid){
                        row[i]++;
                    }
                    else break;
                }
            }
            for(ll i=2;i<=H;i++){
                row[i]=min(row[i],row[i-1]);
            }
            ll mn=1e9+5,mx=0;
            for(ll i=1;i<=H;i++){
                for(ll j=row[i]+1;j<=W;j++){
                    mn=min(mn,a[i][j]);
                    mx=max(mx,a[i][j]);
                }
            }
            if(row[x]>=y&&(mx==0||mx-mn<=mid)){
                ok=true;
            }
        }
        if(ok){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l;
}

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

joioi.cpp: In function 'int main()':
joioi.cpp:73:13: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             if(row[x]>=y&&(mx==0||mx-mn<=mid)){
      |             ^~
joioi.cpp:73:21: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |             if(row[x]>=y&&(mx==0||mx-mn<=mid)){
      |                ~~~~~^

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