第８回日本情報オリンピック 本選 「認証レベル」

頭が悪い。

解法：
priority_queueと、二分探索をもちいた。
おそらくJOI解説とほとんどおんなじ。
気が向いたら詳しく説明します。

priority_queue、大きいほうからでてくるのすっかり忘れてましたね

#include <cstdio>
#include <utility>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int INF = 1000000000;

typedef pair<int,int> P;
typedef pair<int,P> PP;

int dx[5] = {0,1,0,-1};
int dy[5] = {1,0,-1,0};

bool ch1[503][503];
bool ch2[503][503];

int r,w1,w2,h1,h2,x1,x2,y1,y2;

int m1[503][503];
int m2[503][503];

int main(){
  
  while(1){
 scanf("%d",&r);
 if(r == 0)break;
 int ans = INF;
 scanf("%d%d%d%d",&w1,&h1,&x1,&y1);
 
 for(int i = 1;i <= h1;i++){
   for(int j = 1;j <= w1;j++){
     scanf("%d",&m1[i][j]);
     ch1[i][j] = false;
   }
 }
 
 vector<P> dt;
 
 dt.push_back(P(0,0));
 int nau = 0;
 int co=0;
 priority_queue<PP,vector<PP>,greater<PP> > que;
 que.push(PP(1,P(x1,y1)));
 while(que.size()){
   PP tmp = que.top(); que.pop();
   nau = tmp.first;
   co++;
   ch1[tmp.second.second][tmp.second.first] = true;
   for(int i = 0;i < 4;i++){
    int nx = tmp.second.first + dx[i];
    int ny = tmp.second.second + dy[i];
    if(nx >= 1 && nx <= w1 && ny >= 1 && ny <= h1 && ch1[ny][nx] == false ){
      que.push(PP(m1[ny][nx],P(nx,ny)));
      ch1[ny][nx] = true;
    }
   }
	
   while(que.size()){
     if(nau >= que.top().first){
       co++;
       PP tmp2 = que.top();
       ch1[tmp2.second.second][tmp2.second.first] = true;
       que.pop();
        for(int i = 0;i < 4;i++){
	  int nx = tmp2.second.first + dx[i];
	  int ny = tmp2.second.second + dy[i];
	  if(nx >= 1 && nx <= w1 && ny >= 1 && ny <= h1 && ch1[ny][nx] == false ){
	    que.push(PP(m1[ny][nx],P(nx,ny)));
	    ch1[ny][nx] = true;
	  }
	}
     }else{
       break;
     }
   }
   
   dt.push_back(P(nau,co));
   
 }
 
 
 
 scanf("%d%d%d%d",&w2,&h2,&x2,&y2);
 
 for(int i = 1;i <= h2;i++){
   for(int j = 1;j <= w2;j++){
    scanf("%d",&m2[i][j]);
    ch2[i][j] = false;
   }
 }


 nau = 0;
 co=0;
 que.push(PP(1,P(x2,y2)));
 while(que.size()){
   PP tmp = que.top(); que.pop();
   nau = tmp.first;
   co++;
   ch2[tmp.second.second][tmp.second.first] = true;
   for(int i = 0;i < 4;i++){
    int nx = tmp.second.first + dx[i];
    int ny = tmp.second.second + dy[i];
    if(nx >= 1 && nx <= w2 && ny >= 1 && ny <= h2 && ch2[ny][nx] == false ){
      que.push(PP(m2[ny][nx],P(nx,ny)));
      ch2[ny][nx] = true;
    }
   }
	
   while(que.size()){
     if(nau >= que.top().first){
       co++;
       PP tmp2 = que.top();
       ch2[tmp2.second.second][tmp2.second.first] = true;
       que.pop();
        for(int i = 0;i < 4;i++){
	  int nx = tmp2.second.first + dx[i];
	  int ny = tmp2.second.second + dy[i];
	  if(nx >= 1 && nx <= w2 && ny >= 1 && ny <= h2 && ch2[ny][nx] == false ){
	    que.push(PP(m2[ny][nx],P(nx,ny)));
	    ch2[ny][nx] = true;
	  }
	}
     }else{
     break;
     }
   }
   
   int lb = 0,ub = dt.size();
   while(ub - lb > 1){
    int mid = (lb + ub) / 2;
    if(dt[mid].second + co >= r){
      ub = mid;
    }else{
      lb = mid;
    }
   }
   if(dt[ub].second + co >= r){
    ans = min(ans,nau + dt[ub].first);
   }
 }
 
 printf("%d\n",ans);
  }
 
 return 0;
}