管理人の独り言（プログラミング関連）

1526： ◆adhRKFl5jU：2009/03/01(日) 18:33:58: jid27
問題番号 10
点数 50
-----
// O(NMlogM)

#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

const int INF = 1000000010;
const int MAX_N = 1000;
const int MAX_M = 1000;

int N, M, X[2][MAX_M + 10];
int dp[2][MAX_M + 10][MAX_N + 10];

int main() {
scanf("%d%d", &N, &M);
assert(M <= MAX_M && N <= MAX_N);

for (int i = 1; i <= M; i++) scanf("%d%d", &X[0][i], &X[1][i]);

sort(&X[0][1], &X[0][M + 1]);
sort(&X[1][1], &X[1][M + 1]);

dp[0][1][0] = dp[1][1][0] = INF;

for (int k = 0; k <= 1; k++) {
for (int i = 2; i <= M; i++) {
dp[k][i][0] = INF;
for (int j = 1; j <= N; j++) {
dp[k][i][j] = INF;
int lo = 1, up = i;
while (up - lo > 1) {
int mid = (lo + up) / 2;
if (dp[k][mid][j - 1] >= X[k][i] - X[k][mid]) up = mid;
else lo = mid;
}
dp[k][i][j] = min(max(dp[k][lo - 1][j - 1], X[k][i] - X[k][lo]),
max(dp[k][up - 1][j - 1], X[k][i] - X[k][up]));
}
}
}

int ans = INF;
for (int i = 1; i + 1 <= N; i++)
ans = min(ans, max(dp[0][M][i], dp[1][M][N - i]));

printf("%d\n", ans);

return 0;
}

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）

掲示板管理者へ連絡無料レンタル掲示板