結果
| 問題 | No.1715 Dinner 2 |
| ユーザー |
👑  ygussany
|
| 提出日時 | 2021-10-22 12:54:14 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 4,678 bytes |
| コンパイル時間 | 496 ms |
| コンパイル使用メモリ | 36,224 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-23 03:54:22 |
| 合計ジャッジ時間 | 1,511 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 38 |
ソースコード
// O(N * log(N) + (D + N) * log(|max_ans|)) time solution#include <stdio.h>#define N_MAX 1000#define D_MAX 1000#define P_MAX 100000typedef struct {int key, id;} data;void merge_sort(int n, data x[]){static data y[N_MAX + 1];if (n <= 1) return;merge_sort(n / 2, &(x[0]));merge_sort((n + 1) / 2, &(x[n/2]));int i, p, q;for (i = 0, p = 0, q = n / 2; i < n; i++) {if (p >= n / 2) y[i] = x[q++];else if (q >= n) y[i] = x[p++];else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];}for (i = 0; i < n; i++) x[i] = y[i];}void chmax(long long* a, long long b){if (*a < b) *a = b;}int main(){int i, N, D, P[N_MAX + 1], Q[N_MAX + 1];data d[N_MAX + 1];scanf("%d %d", &N, &D);for (i = 0; i < N; i++) scanf("%d %d", &(d[i].key), &(d[i].id));merge_sort(N, d);for (i = 0; i < N; i++) {P[i+1] = d[i].key;Q[i+1] = d[i].id;}P[0] = 0;Q[0] = -P_MAX;const int sup = P_MAX + 1;int j, argmax[N_MAX + 1][3] = {}, argmax_inv[N_MAX + 1][3][2] = {};for (i = 1; i <= N; i++) {for (j = 0; j < 3; j++) argmax[i][j] = argmax[i-1][j];j = argmax[i-1][0];if (Q[i] - P[i] > Q[j] - P[j]) {argmax_inv[i][0][0] = P[i];argmax_inv[argmax[i][0]][0][1] = P[i] - 1;argmax_inv[argmax[i][0]][1][0] = P[i];argmax_inv[argmax[i][1]][1][1] = P[i] - 1;argmax_inv[argmax[i][1]][2][0] = P[i];argmax_inv[argmax[i][2]][2][1] = P[i] - 1;argmax[i][2] = argmax[i][1];argmax[i][1] = argmax[i][0];argmax[i][0] = i;continue;}j = argmax[i-1][1];if (Q[i] - P[i] > Q[j] - P[j]) {argmax_inv[i][1][0] = P[i];argmax_inv[argmax[i][1]][1][1] = P[i] - 1;argmax_inv[argmax[i][1]][2][0] = P[i];argmax_inv[argmax[i][2]][2][1] = P[i] - 1;argmax[i][2] = argmax[i][1];argmax[i][1] = i;continue;}j = argmax[i-1][2];if (Q[i] - P[i] > Q[j] - P[j]) {argmax_inv[i][2][0] = P[i];argmax_inv[argmax[i][2]][2][1] = P[i] - 1;argmax[i][2] = i;}}argmax_inv[argmax[N][0]][0][1] = sup;argmax_inv[argmax[N][1]][1][1] = sup;argmax_inv[argmax[N][2]][2][1] = sup;long long l = 1, r = (long long)D * P[2], m, dp[D_MAX + 1][4], tmp;int h, k[D_MAX + 1][4], x, last[4][2];while (l < r) {m = (l + r) / 2;for (j = 0; j < 3; j++) {dp[0][j] = -1;k[0][j] = 0;last[j][0] = -1;last[j][1] = -1;}dp[0][3] = m;for (k[0][3] = 0; k[0][3] < N && P[k[0][3] + 1] <= m; k[0][3]++);last[3][0] = 0;last[3][1] = -1;for (i = 1, dp[0][3] = m; i <= D; i++) {for (j = 0; j < 4; j++) dp[i][j] = -1;for (j = 0; j < 4; j++) {if (k[i-1][j] == 0) continue;for (h = 0; h < 3; h++) {x = argmax[k[i-1][j]][h];if (h == j || x == 0) continue;tmp = dp[i-1][j] - P[x];if (tmp < 0) continue;else tmp += Q[x];if (argmax_inv[x][0][0] <= tmp && (argmax_inv[x][0][1] == sup || tmp <= argmax_inv[x][0][1])) chmax(&(dp[i][0]), tmp);if (argmax_inv[x][1][0] <= tmp && (argmax_inv[x][1][1] == sup || tmp <= argmax_inv[x][1][1])) chmax(&(dp[i][1]), tmp);if (argmax_inv[x][2][0] <= tmp && (argmax_inv[x][2][1] == sup || tmp <= argmax_inv[x][2][1])) chmax(&(dp[i][2]), tmp);if (!(argmax_inv[x][0][0] <= tmp && (argmax_inv[x][0][1] == sup || tmp <= argmax_inv[x][0][1])) && !(argmax_inv[x][1][0] <= tmp&& (argmax_inv[x][1][1] == sup || tmp <= argmax_inv[x][1][1])) && !(argmax_inv[x][2][0] <= tmp && (argmax_inv[x][2][1] == sup|| tmp <= argmax_inv[x][2][1]))) chmax(&(dp[i][3]), tmp);}}if (dp[i][0] + dp[i][1] + dp[i][2] + dp[i][3] == -4) break;for (j = 0; j < 4; j++) {if (dp[i][j] < 0) continue;else if (last[j][0] < 0) {for (k[i][j] = 0; k[i][j] < N && P[k[i][j] + 1] <= dp[i][j]; k[i][j]++);last[j][0] = i;} else if (last[j][1] < 0) {for (k[i][j] = 0; k[i][j] < N && P[k[i][j] + 1] <= dp[i][j]; k[i][j]++);last[j][1] = i;} else {if (dp[i][j] > dp[last[j][0]][j] && dp[i][j] > dp[last[j][1]][j]) break;else if (dp[last[j][0]][j] > dp[last[j][1]][j]) {if (dp[i][j] <= dp[last[j][1]][j]) for (k[i][j] = k[last[j][1]][j]; k[i][j] > 0 && P[k[i][j]] > dp[i][j]; k[i][j]--);else for (k[i][j] = k[last[j][0]][j]; k[i][j] > 0 && P[k[i][j]] > dp[i][j]; k[i][j]--);last[j][0] = i;} else {if (dp[i][j] <= dp[last[j][0]][j]) for (k[i][j] = k[last[j][0]][j]; k[i][j] > 0 && P[k[i][j]] > dp[i][j]; k[i][j]--);else for (k[i][j] = k[last[j][1]][j]; k[i][j] > 0 && P[k[i][j]] > dp[i][j]; k[i][j]--);last[j][1] = i;}}}if (j < 4) {i = D + 1;break;}}if (i > D) r = m;else l = m + 1;}printf("%d\n", -l);fflush(stdout);return 0;}