Submission #68039124
Source Code Expand
Copy
#include <stdio.h>#include <stdlib.h>#include <inttypes.h>struct sentakusi_s {uint64_t A, B;};int cmp(const void* x, const void* y) {struct sentakusi_s a = *(const struct sentakusi_s*)x, b = *(const struct sentakusi_s*)y;return a.A < b.A ? -1 : a.A > b.A;}uint64_t N;int M;struct sentakusi_s S[212345];uint64_t min_syouhi[212345];uint64_t min_syouhi_cost[212345];int main(void) {
#include <stdio.h> #include <stdlib.h> #include <inttypes.h> struct sentakusi_s { uint64_t A, B; }; int cmp(const void* x, const void* y) { struct sentakusi_s a = *(const struct sentakusi_s*)x, b = *(const struct sentakusi_s*)y; return a.A < b.A ? -1 : a.A > b.A; } uint64_t N; int M; struct sentakusi_s S[212345]; uint64_t min_syouhi[212345]; uint64_t min_syouhi_cost[212345]; int main(void) { int i; uint64_t cur, ans; if (scanf("%" SCNu64 "%d", &N, &M) != 2) return 1; for (i = 0; i < M; i++) { if (scanf("%" SCNu64 "%" SCNu64, &S[i].A, &S[i].B) != 2) return 1; } qsort(S, M, sizeof(*S), cmp); min_syouhi[0] = S[0].A - S[0].B; min_syouhi_cost[0] = S[0].A; for (i = 1; i < M; i++) { min_syouhi[i] = S[i].A - S[i].B; min_syouhi_cost[i] = S[i].A; /* 前のほうが消費量が少ない、または同じ (昇順ソート済なので、コストが多くない) */ if (min_syouhi[i] >= min_syouhi[i - 1]) { min_syouhi[i] = min_syouhi[i - 1]; min_syouhi_cost[i] = min_syouhi_cost[i - 1]; } } cur = N; ans = 0; for (i = M - 1; i >= 0; i--) { if (cur >= min_syouhi_cost[i]) { /* 瓶の数が最適操作のコスト未満になるまで削りたい */ /* まずは、最適操作のコスト「以下」まで削る */ uint64_t num_sousa = (cur - min_syouhi_cost[i] + min_syouhi[i] - 1) / min_syouhi[i]; cur -= min_syouhi[i] * num_sousa; ans += num_sousa; /* 上の操作で瓶の数がコストちょうどになった場合、さらにもう1回操作する */ if (cur == min_syouhi_cost[i]) { cur -= min_syouhi[i]; ans++; } } } printf("%" PRIu64 "\n", ans); return 0; } /* 等価交換なので、「瓶入りコーラ」と「空き瓶」は同一視していい 今とれる選択肢の中で、最も瓶の消費が少ない選択肢を選ぶ そうでない選択肢を選んでも有利にならない (瓶の消費が少ない選択肢のほうが、同じシールの枚数で、残りの瓶が少なくない状態にできる) */
Submission Info
Submission Time | |
---|---|
Task | D - Get Many Stickers |
User | mikecat |
Language | C (gcc 12.2.0) |
Score | 400 |
Code Size | 2087 Byte |
Status | AC |
Exec Time | 64 ms |
Memory | 8048 KiB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt |
All | 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 02_random2_05.txt, 02_random2_06.txt, 02_random2_07.txt, 02_random2_08.txt, 02_random2_09.txt, 02_random2_10.txt, 02_random2_11.txt, 03_random3_00.txt, 03_random3_01.txt, 03_random3_02.txt, 03_random3_03.txt, 03_random3_04.txt, 04_handmade_00.txt, 04_handmade_01.txt, 04_handmade_02.txt, 04_handmade_03.txt, 04_handmade_04.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00.txt | AC | 0 ms | 1604 KiB |
00_sample_01.txt | AC | 1 ms | 1628 KiB |
00_sample_02.txt | AC | 0 ms | 1740 KiB |
01_random_00.txt | AC | 31 ms | 4804 KiB |
01_random_01.txt | AC | 43 ms | 5820 KiB |
01_random_02.txt | AC | 53 ms | 6868 KiB |
01_random_03.txt | AC | 47 ms | 7968 KiB |
01_random_04.txt | AC | 47 ms | 7876 KiB |
01_random_05.txt | AC | 47 ms | 7968 KiB |
02_random2_00.txt | AC | 60 ms | 7968 KiB |
02_random2_01.txt | AC | 59 ms | 7876 KiB |
02_random2_02.txt | AC | 59 ms | 7996 KiB |
02_random2_03.txt | AC | 59 ms | 8048 KiB |
02_random2_04.txt | AC | 59 ms | 7832 KiB |
02_random2_05.txt | AC | 59 ms | 7884 KiB |
02_random2_06.txt | AC | 61 ms | 7900 KiB |
02_random2_07.txt | AC | 60 ms | 7904 KiB |
02_random2_08.txt | AC | 60 ms | 7876 KiB |
02_random2_09.txt | AC | 63 ms | 7820 KiB |
02_random2_10.txt | AC | 64 ms | 7888 KiB |
02_random2_11.txt | AC | 64 ms | 8000 KiB |
03_random3_00.txt | AC | 63 ms | 7904 KiB |
03_random3_01.txt | AC | 64 ms | 7872 KiB |
03_random3_02.txt | AC | 64 ms | 7992 KiB |
03_random3_03.txt | AC | 64 ms | 7896 KiB |
03_random3_04.txt | AC | 63 ms | 8048 KiB |
04_handmade_00.txt | AC | 24 ms | 7852 KiB |
04_handmade_01.txt | AC | 25 ms | 7988 KiB |
04_handmade_02.txt | AC | 0 ms | 1724 KiB |
04_handmade_03.txt | AC | 0 ms | 1640 KiB |
04_handmade_04.txt | AC | 64 ms | 7880 KiB |