JOI'09 本選5問目 認証レベル

問題概要

事務所の入り口から,持ってる身分証のレベル以下の部屋にだけ入れる.
2つの事務所それぞれに入って合計R部屋以上巡ることができるように身分証を2つ渡すとき,レベルの和の最小値はいくつか.

解法

1つの身分証で2つの事務所とも回れると誤読した結果,二分探索で境界を判定する実装をするも,サンプルが合わない(それはそう).
考え直すと,それぞれの事務所で必要なレベルはDijkstra的な探索で巡る部屋数全てをO(HW log HW)で求めることができる.
これらを組み合わせて最小値を取れば良い.
横縦の順に情報を入力する問題は嫌いだ.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
bool inboard(int x,int y,int h,int w){
    return 0<=x&&x<h&&0<=y&&y<w;
}
vi f(int r){
    int h,w;
    cin>>w>>h;
    int sx,sy;
    cin>>sy>>sx;
    sx--;sy--;
    vvi vec(h,vi(w));
    REP(i,h){
        REP(j,w){
            cin>>vec[i][j];
        }
    }
    int maxcost=0;
    vi ans(r+1,INF);
    int cnt=0;
    ans[0]=0;
    priority_queue<PP,vpp,greater<PP>> que;
    vvi visited(h,vi(w));
    que.push(PP(vec[sx][sy],P(sx,sy)));
    while(que.size()){
        PP p=que.top();que.pop();
        P v=p.se;
        if(visited[v.fi][v.se]){
            continue;
        }
        visited[v.fi][v.se]=true;
        cnt++;
        chmax(maxcost,vec[v.fi][v.se]);
        ans[cnt]=maxcost;
        if(cnt==r){
            break;
        }
        REP(k,4){
            int x=v.fi+dx[k];
            int y=v.se+dy[k];
            if(!inboard(x,y,h,w)){
                continue;
            }
            if(visited[x][y]){
                continue;
            }
            que.push(PP(vec[x][y],P(x,y)));
        }
    }
    return ans;
}
int main(){
    int r;
    cin>>r;
    vi a=f(r);
    vi b=f(r);
    int ans=INF;
    cerr<<endl;
    REP(i,r+1){
        chmin(ans,a[i]+b[r-i]);
    }
    cout<<ans<<endl;
    return 0;
}