50056. How Much Money Can You Make_
難度：2/51
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>
#include <limits.h>
typedef struct s_material{
char name[52];
int qty;
int price;
} s_material;
typedef struct s_product{
char name[52];
struct s_material* mtrl_used[128];
int mtrl_used_qty[128];
int mtrl_len;
int price;
int profit;
} s_product;
int n, m;
s_material material[128];
s_product product[128];
static inline int max(int a, int b) {return (a > b) ? a : b;}
static inline int min(int a, int b) {return (a < b) ? a : b;}
static inline int find_material(char st[52]){
for(int i = 0; i < n; i++){
if(strcmp(material[i].name, st) == 0) return i;
}
return -1;
}
static inline void get_material(s_material* mtrl){
scanf("%s %d %d", mtrl->name, &(mtrl->qty), &(mtrl->price));
}
static inline void get_product(s_product* p){
scanf("%s %d", p->name, &(p->mtrl_len));
for(int i = 0; i < p->mtrl_len; i++){
char st[52];
scanf("%s %d", st, &p->mtrl_used_qty[i]);
p->mtrl_used[i] = &material[find_material(st)];
}
scanf("%d", &(p->price));
}
static inline void ipt(){
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++){
get_material(&material[i]);
}
for(int i = 0; i < m; i++){
get_product(&product[i]);
}
}
static inline void get_profit(s_product *p){
int max_can_make = INT_MAX;
for(int i = 0; i < p->mtrl_len; i++){
max_can_make = min(max_can_make, (p->mtrl_used[i])->qty / (p->mtrl_used_qty[i]));
}
// printf("%d\n", max_can_make);
int cost = 0;
for(int i = 0; i < p->mtrl_len; i++){
cost += (p->mtrl_used[i])->price * (p->mtrl_used_qty[i]);
}
p->profit = max((p->price - cost) * max_can_make, 0);
}
int cmp(const void* a, const void* b){
s_product* pa = (s_product*)a;
s_product* pb = (s_product*)b;
if(pa->profit < pb->profit) return 1;
else if(pa->profit > pb->profit) return -1;
else return strcmp(pa->name, pb->name);
}
int main(){
ipt();
for(int i = 0; i < m; i++){
get_profit(&product[i]);
}
qsort(product, m, sizeof(s_product), cmp);
printf("%s %d\n", product[0].name, product[0].profit);
}