[SWEA] 1952 수영장

Time Lapse :23min 5sec

1952.c

1
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
/*
* DP solution
*/
#include <stdio.h>
#define gc() getchar_unlocked()
#define pc(x) putchar_unlocked(x)
#define reg register
int fRI() {
reg int N = gc(), r = 0;
for (;48 > N || N > 57; N = gc());
do {
r = (r << 3) + (r << 1) + (N & 0b1111); N = gc();
} while (48 <= N);
return r;
}
void fWI(int tc) {
reg int r = 0, c = 0;
while (!(tc % 10)) { c++; tc /= 10; }
while (tc) { r = (r << 3) + (r << 1) + (tc % 10); tc /= 10; }
while (r) { pc(r % 10 | 0b110000); r /= 10; }
while (c--) pc(0x30);
}
int main(int argc, char** argv){
reg int tc = 1, T = fRI(), answer, d, m, m3;
int DP[13];
while(T--){
d = fRI(); m = fRI(); m3 = fRI(); answer = fRI();
DP[1] = fRI(); DP[1] = DP[1]*d > m ? m : DP[1]*d;
DP[2] = fRI(); DP[2] = DP[2]*d > m? m+DP[1] : DP[2]*d+DP[1];
for(reg int i = 3 ; i <= 12; i++) {
DP[i] = fRI();
DP[i] = DP[i]*d < m ? DP[i]*d : m;
DP[i] = DP[i-3]+m3 > DP[i-1] + DP[i] ? DP[i-1] + DP[i] : DP[i-3]+m3;
}
pc(0x23); fWI(tc++); pc(32); fWI(answer > DP[12] ? DP[12] : answer); pc(0x0A);
}
}

/* DFS
#include <stdio.h>
#define gc() getchar_unlocked()
#define pc(x) putchar_unlocked(x)
#define reg register
int cost[3];
int month[15] = {0};
int answer;
int fRI() {
reg int N = gc(), r = 0;
for (;48 > N || N > 57; N = gc());
do {
r = (r << 3) + (r << 1) + (N & 0b1111); N = gc();
} while (48 <= N);
return r;
}
void fWI(int tc) {
reg int r = 0, c = 0;
while (!(tc % 10)) { c++; tc /= 10; }
while (tc) { r = (r << 3) + (r << 1) + (tc % 10); tc /= 10; }
while (r) { pc(r % 10 | 0b110000); r /= 10; }
while (c--) pc(0x30);
}
void DFS(int cm, int cc){
if(cc>answer) return;
if(cm >= 12) { answer = answer > cc? cc : answer; return;}
if (month[cm] + month[cm + 1] + month[cm + 2] > cost[2])
DFS(cm + 3, cc + cost[2]);
DFS(cm + 1, cc + month[cm]);
}
int main(int argc, char** argv){
reg int tc = 1, T = fRI();
while(T--){
cost[0] = fRI(); cost[1] = fRI(); cost[2] = fRI(); answer = fRI();
for(int i = 0 ; i < 12; i++) {
month[i] = fRI();
month[i] = month[i]*cost[0] < cost[1] ? month[i]*cost[0] : cost[1];
}
DFS(0,0);
pc(0x23); fWI(tc++); pc(32); fWI(answer); pc(0x0A);
}
}
*/
Author: Song Hayoung
Link: https://songhayoung.github.io/2020/08/04/PS/SWEA/1952/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.