Competitive-Programming/easy_problem.cpp at master · Code-Cube-NITP/Competitive-Programming · GitHub

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
#include<bits/stdc++.h>
#definefastioios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#defineendl'\n'
#defineintlonglongint
usingnamespacestd;
#definepii pair <int, int>
#definemii map<int, int>
#definepb push_back
#definedeb(x) cout << #x << "" << x << endl
#definedeb2(x, y) cout << #x << "" << x << "" << #y << "" << y << endl
#defineLoop(s, e, itr) for (int itr = s; itr < e; itr++)
#defineloop(n) for(int i = 0; i < n; i++)
#definevin vector<int>
#definew(t) int tc; cin >> tc; for(int t = 1; t <= tc; t++)
#definevec vector
#definemk_arr(n, t, s) t* n = new t[s]; loop(s) cin >> n[i];
#definemi_arr(n, s) int* n = newint[s]; loop(s) cin >> n[i];
#definearr_out(n, s) Loop(0, s, lout) cout << n[lout] << "";
#definepi(x) printf("%lld ", x);
#definemod1000000007


// #define forn(i, n) for (int i = 0; i < int(n); i++)

constint N = 100 * 1000 + 13;
constlonglongINF64 = 1e18;

int n;
string s;
int a[N];
longlong dp[N][5];

const string h = "hard";

int32_tmain() {
scanf("%d", &n);
staticchar buf[N];
scanf("%s", buf);
	s = buf;
loop(n)
scanf("%d", &a[i]);

loop(N) Loop(0,5,j) dp[i][j] = INF64;
	dp[0][0] = 0;
loop(n) Loop(0,4,j){
 dp[i + 1][j + (s[i] == h[j])] = min(dp[i + 1][j + (s[i] == h[j])], dp[i][j]);
 dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i]);
	}

printf("%lld\n", *min_element(dp[n], dp[n] + 4));
return0;
}