## Editorial for VOI 12 Bài 6 - Qua cầu

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

int n,m,r[10100],t[10100],d[100100],l[100100];
char s[100100];

int calc(int step)
{
if (d[step]) return d[step];
int res=0,pos=0;
while (1)
{
res++;
if (pos+step>m) return res;
pos=l[pos+step];
}
}

int main()
{
cin >> n >> m;
for (int i=1;i<=n;i++) scanf("%d",&r[i]);
scanf("%s",&s);

for (int i=1;i<=m;i++) l[i]=(s[i-1]=='0'?i:l[i-1]);
for (int i=1;i<=n;i++) t[i]=calc(r[i]);

int ans=0;
sort(t+1,t+n+1);
while (n>3) ans+=min(t[1]+t[n-1],t[2]*2)+t[1]+t[n], n-=2;
ans+=t[2]+(n==3?t[1]+t[3]:0);

cout << ans << endl;
}


#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 200004;
using namespace std;
int t[N], r[N], prev[N], f[N];
bool damaged[N];
int n, m;

int simul(int jump) {
int timer = 0;
for(int i = 0; i <= m; ) {
timer++;
if (damaged[i + jump])
i = prev[i + jump];
else
i += jump;
}
return timer;
}

int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
REP(i, 1, n) cin >> r[i];
REP(i, 1, m) {
char ch;
cin >> ch;
if (ch == '1')
damaged[i] = 1;
}
sort(r + 1, r + 1 + n, greater<int>());
REP(i, 1, m)
if (!damaged[i - 1])
prev[i] = i - 1;
else
prev[i] = prev[i - 1];
REP(i, 1, n) {
if (r[i] == r[i - 1])
t[i] = t[i - 1];
else
t[i] = simul(r[i]);
}
f[1] = t[1]; f[2] = t[2]; f[3] = f[2] + t[3] + t[1];
REP(i, 4, n)
f[i] = min(f[i - 1] + t[i] + t[1], f[i - 2] + t[1] + t[2] + t[2] + t[i]);
cout << f[n];
return 0;
}


#### Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
if (REACHEOF) return 0;\
memset(BUF,0,sizeof BUF);\
if (inpzzz != BUFSIZE) REACHEOF = true;\
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}

const long double PI = acos((long double) -1.0);

int n, m, f[100111], a[10111], x[111], r[10111];
char s[100111];

int main() {
scanf("%d%d", &n, &m);
FOR(i,1,n) scanf("%d", &r[i]);
scanf("%s", &s[1]);

FOR(l,1,100) {
f[0] = 0;
int j = 0;
FOR(i,1,m+1) {
while (s[j] == '1' || i - j > l) ++j;
f[i] = f[j] + 1;
}

x[l] = f[m+1];
}
FOR(i,1,n)
a[i] = x[r[i]];

sort(a+1, a+n+1);

f[1] = a[1];
f[2] = a[2];
FOR(i,3,n) {
f[i] = a[i] + a[1] + f[i-1];
if (i > 3)
f[i] = min(f[i], a[2] + a[1] + a[i] + a[2] + f[i-2]);
}
cout << f[n] << endl;
return 0;
}


#### Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 10011
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,m;
int r[maxn],a[maxn],d[111];
string s;

int main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&r[i]);
cin >> s;
for(int i = 1; i <= 100; i++){
d[i] = 1;
int start = -1, t;
while(true){
t = min(m,start + i);
if( t == m){
break;
}
while(s[t] == '1') t--;
if(t == start){
d[i] = -1;
break;
}
d[i]++;
start = t;
}
}
for(int i = 1; i <= n; i++) a[i] = d[r[i]];
sort(a + 1, a + n + 1);
if(n == 0) printf("0");
else if( n == 1){
printf("%d",a[1]);
}
else{
int kq = a[2];
for(int i = n; i > 3; i-=2){
if(a[1] + a[i - 1] < 2 * a[2])
kq += 2 * a[1] + a[i - 1] + a[i];
else kq += a[1] + 2 * a[2] + a[i];
}
if(n & 1) kq += a[1] + a[3];
printf("%d",kq);
}
}


#### Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#define MAX   100100
#define MAXS   101
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
char s[MAX];
int r[MAXS];
int v[MAX];
int t[MAX];
int f[MAX];
int pre[MAX];
int m,n;
void init(void) {
scanf("%d",&n);
scanf("%d",&m);
FOR(i,1,n) scanf("%d",&v[i]);
scanf("%s",s+1);
s[m+1]='0';
pre[1]=0;
FOR(i,2,m+2) {
if (s[i-1]=='0') pre[i]=i-1;
else pre[i]=pre[i-1];
}
}
int timereq(int x) {
int cur=0;
int cnt=0;
while (cur<=m) {
cnt++;
if (cur==pre[min(cur+x+1,m+2)]) return (-1);
cur=pre[min(cur+x+1,m+2)];
}
return (cnt);
}
void precount(void) {
REP(i,MAXS) r[i]=timereq(i);
FOR(i,1,n) t[i]=r[v[i]];
sort(t+1,t+n+1);
}
void optimize(void) {
FOR(i,1,2) f[i]=t[i];
f[3]=t[1]+t[2]+t[3];
FOR(i,4,n) f[i]=min(f[i-1]+t[1]+t[i],f[i-2]+t[i]+2*t[2]+t[1]);
printf("%d",f[n]);
}
int main(void) {
init();
precount();
optimize();
return 0;
}