Submission #68039124

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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

Judge Result