結果
問題 | No.1736 Princess vs. Dragoness |
ユーザー |
👑 |
提出日時 | 2021-11-12 21:40:32 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 1,776 bytes |
コンパイル時間 | 824 ms |
コンパイル使用メモリ | 31,360 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-25 17:35:29 |
合計ジャッジ時間 | 1,514 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <stdio.h>typedef struct {int key, id;} data;typedef struct {data obj[100001];int size;} max_heap;void push(max_heap* h, data x){int i = ++(h->size), j = i >> 1;data tmp;h->obj[i] = x;while (j > 0) {if (h->obj[i].key > h->obj[j].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j >>= 1;} else break;}}data pop(max_heap* h){int i = 1, j = 2;data output = h->obj[1], tmp;h->obj[1] = h->obj[(h->size)--];while (j <= h->size) {if (j < h->size && h->obj[j^1].key > h->obj[j].key) j ^= 1;if (h->obj[j].key > h->obj[i].key) {tmp = h->obj[j];h->obj[j] = h->obj[i];h->obj[i] = tmp;i = j;j <<= 1;} else break;}return output;}int main(){int i, N, A, B, X, Y, H[100001];scanf("%d %d %d %d %d", &N, &A, &B, &X, &Y);for (i = 1; i <= N; i++) scanf("%d", &(H[i]));int j, a, l = 0, r = 1 << 30, m, YY, Z[100001];max_heap h;data d;while (l < r) {m = (l + r) / 2;h.size = 0;for (i = 1; i <= N; i++) {Z[i] = H[i] - m;if (Z[i] <= 0) continue;d.key = Z[i];d.id = i;push(&h, d);}for (i = 0; i < A; i++) {if (h.size == 0) break;d = pop(&h);j = d.id;Z[j] -= X;if (Z[j] <= 0) continue;d.key -= X;push(&h, d);}if (i < A) {r = m;continue;}for (i = 0, j = 1; i < B; i++) {YY = Y;while (YY > 0) {while (j <= N && Z[j] <= 0) j++;if (j <= N) {if (Z[j] <= YY) {YY -= Z[j];Z[j] = 0;} else {Z[j] -= YY;YY = 0;}} else break;}if (YY > 0) break;}while (j <= N && Z[j] <= 0) j++;if (j > N) r = m;else l = m + 1;}if (l == 0) printf("Yes\n");else printf("No\n");fflush(stdout);return 0;}