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) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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
AC × 3
AC × 31
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


2025-07-30 (Wed)
07:54:07 +09:00