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;
}

Code mẫu của ladpro98

#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;

//Buffer reading
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);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        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;\
}
//End of buffer reading

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;
}