結果

問題 No.2157 崖
ユーザー tnakao0123
提出日時 2022-12-11 21:36:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 385 ms / 6,000 ms
コード長 1,350 bytes
コンパイル時間 840 ms
コンパイル使用メモリ 60,800 KB
実行使用メモリ 20,480 KB
最終ジャッジ日時 2024-10-15 17:02:58
合計ジャッジ時間 8,742 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 2157.cc:  No.2157 崖 - yukicoder
 */

#include<cstdio>
#include<deque>
#include<algorithm>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 1500;
const int MAX_M = 1500;
const int INF = 1 << 30;

/* typedef */

typedef pair<int,int> pii;
typedef deque<pii> dqpii;

/* global variables */

int ds[MAX_N][MAX_M], dp[MAX_N][MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) scanf("%d", ds[i] + j);
    sort(ds[i], ds[i] + m);
  }

  for (int i = 1; i < n; i++) {
    dqpii q;
    for (int j0 = 0, j1 = 0; j1 < m; j1++) {
      while (j0 < m && ds[i - 1][j0] <= ds[i][j1]) {
	while (! q.empty() && q.back().first >= dp[i - 1][j0]) q.pop_back();
	q.push_back(pii(dp[i - 1][j0], ds[i - 1][j0]));
	j0++;
      }

      dp[i][j1] = INF;
      if (! q.empty()) {
	pii u = q.front(); q.pop_front();
	int ud = max(u.first, ds[i][j1] - u.second);
	while (! q.empty()) {
	  pii v = q.front();
	  int vd = max(v.first, ds[i][j1] - v.second);
	  if (ud >= vd) {
	    q.pop_front();
	    u = v, ud = vd;
	  }
	  else
	    break;
	}
	q.push_front(u);
	dp[i][j1] = ud;
      }
    }
  }

  int mind = *min_element(dp[n - 1], dp[n - 1] + m);
  printf("%d\n", (mind < INF) ? mind : -1);
  
  return 0;
}
0