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 <cstdio>
#include <queue>
using namespace std;

int n,st[100100],head=1,tail,pos[100100],active[100100];
long long s[100100],f[100100],m;
priority_queue < pair<long long,int> > q;

int main()
{
    int x;
    cin >> n >> m;
    for (int i=1,j=0;i<=n;i++) 
    {
        scanf("%d",&x);
        if (x>m)
        {
            cout << -1 << endl;
            return 0;
        }

        while (tail>=head && x>=st[tail]) active[pos[tail--]]=0;
        st[++tail]=x; pos[tail]=i; 

        s[i]=s[i-1]+x;
        while (s[i]-s[j]>m) j++;
        while (head<=tail && pos[head]<=j) active[pos[head++]]=0;
        active[pos[head]]=0;

        f[i]=f[j]+st[head];
        while (!q.empty())
        {
            pair <long long,int> u=q.top();
            if (!active[u.second]) q.pop();
            else 
            {
                f[i]=min(f[i],-u.first);
                break;
            }
        }
        if (tail>head) 
        {
            f[i]=min(f[i],f[pos[tail-1]]+st[tail]);
            q.push(make_pair(-f[pos[tail-1]]-st[tail],i));
        }
        else q.push(make_pair(0LL,i));              
        active[i]=1;
    }   
    cout << f[n] << endl;
}

Code mẫu của ladpro98

#include <algorithm>
#include <cstdio>
#include <queue>
#include <iostream>
#define li pair<long long, int>
#define X first
#define Y second
const int N = 100005;
const int oo = 1000000009;
using namespace std;
int Q[N], a[N];
long long sum[N], F[N], v[N];
int n; long long m;

priority_queue <li, vector<li>, greater<li> > heap;
priority_queue <li> heap_max;
int main()
{
    scanf("%d %lld", &n, &m);
    int i;
    for(i=1; i<=n; i++) {
        scanf("%d", &a[i]); if (a[i] > m) {printf("-1"); return 0;}
    }
    for(i=1; i<=n; i++) sum[i] = sum[i-1] + a[i];
    int l = 0, r = 1, lim = 0; li cand; bool found;
    Q[++l] = 0; a[0] = oo;
    for(i=1; i<=n; i++) {
        heap_max.push(li(a[i], i));
        while (l <= r && sum[i] - sum[Q[l]] > m) l++;
        while (l <= r && a[Q[r]] <= a[i]) {v[r] = -oo; r--;}
        while (sum[i] - sum[lim] > m) lim++;
        if (l <= r) {
            heap.push(li(F[Q[r]] + a[i], r));
            v[r] = F[Q[r]] + a[i];
        }
        Q[++r] = i; v[r] = -oo;
        while (heap_max.size()) {
            cand = heap_max.top();
            if (cand.Y <= lim) {
                heap_max.pop();
                continue;
            }
            break;
        }
        F[i] = F[lim] + cand.X;
        if (l == r) continue;
        found = false;
        while (heap.size()) {
            cand = heap.top();
            if (cand.Y < l || v[cand.Y] != cand.X) {
                heap.pop();
                continue;
            }
            found = true; break;
        }
        if (found)
            F[i] = min(F[i], (long long)cand.X);
    }
    cout << F[n] << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>

#define MAXN 100111
#define oo 1000111000111LL
#define SNODE 524288
#define ll long long
#define FOR(i,a,b)  for(int i=a; i<=b; i++)
#define FORD(i,a,b) for(int i=a; i>=b; i--)
#define FORV(i,v)   for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++)
#define CT(i) (i<<1)
#define CP(i) ((i<<1)+1)
using namespace std;

int n,a[MAXN],stack[MAXN],top,start[MAXN];
ll m,s[MAXN],it[SNODE],f[MAXN];

void inp() {
    cin >>n >>m;
    FOR(i,1,n) {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
}

void update(int i,int l,int r,int u,ll k) {
    if (u<l || r<u) return ;
    if (l==r) {
        it[i]=k;
        return ;
    }
    int mid=(l+r)>>1;
    update(CT(i),l,mid,u,k);
    update(CP(i),mid+1,r,u,k);
    it[i]=min(it[CT(i)],it[CP(i)]);
}

ll get(int i,int l,int r,int u,int v) {
    if (v<l || r<u) return oo;
    if (u<=l && r<=v) return it[i];
    int mid=(l+r)>>1;
    return min(get(CT(i),l,mid,u,v),get(CP(i),mid+1,r,u,v));
}

int find(int u) {
    int l=1,r=top, mid=0,res;
    while (l<=r) {
        mid=(l+r)>>1;
        if (stack[mid]>=u) {
            res=mid;
            r=mid-1;
        } else l=mid+1;
    }
    return res;
}

void solve() {
    f[0]=0;
    FOR(i,1,n)
        if (a[i]>m) {
            cout<<-1;
            return ;
        }

    FOR(i,0,SNODE-1) it[i]=oo;

    int j=0;
    FOR(i,1,n) {
        while (s[i]-s[j]>m) j++;
        start[i]=j+1;
    }

    top=0;
    FOR(i,1,n) {
        f[i]=f[i-1]+a[i];
        while (top && a[stack[top]]<a[i]) top--;
        if (!top) f[i] <?= f[start[i]-1]+a[i];
        else if (stack[top]>=start[i]) f[i] <?= f[stack[top]]+a[i];

        stack[++top]=i;
        int u=find(start[i]);

        f[i] <?= get(1,1,n,u,top-2);
        f[i] <?= f[start[i]-1]+a[stack[u]];

        update(1,1,n,top-1,f[stack[top-1]]+a[i]);
    }
    cout<<f[n];
}

int main() {
    inp();
    solve();
    return 0;
}

Code mẫu của ll931110

{$MODE DELPHI}
program CUTSEQS;
const
  input  = '';
  output = '';
  maxn = 100000;
var
  n: integer;
  m: int64;
  max,prev: array[0..maxn] of integer;
  a,F,s: array[0..maxn] of int64;
  time: integer;

procedure init;
var
  fi: text;
  i: integer;
begin
  assign(fi, input);
    reset(fi);

  readln(fi, n, m);
  for i := 1 to n do read(fi, a[i]);

  close(fi);
end;

procedure solve;
var
  fo: text;
  i,t,k: integer;
  maxv: int64;
begin
  assign(fo, output);
    rewrite(fo);

  maxv := 0;
  s[0] := 0;
  for i := 1 to n do
    begin
      if maxv < a[i] then maxv := a[i];
      s[i] := s[i - 1] + a[i];
    end;

  if maxv > m then
    begin
      writeln(fo, -1);
      close(fo);
      exit;
    end;

  fillchar(F, sizeof(F), 0);
  fillchar(max, sizeof(max), 0);

  prev[0] := -1;
  for i := 1 to n do
    begin
      F[i] := F[i - 1] + a[i];

      max[i] := a[i];
      if max[i - 1] < max[i] then max[i - 1] := max[i];

      t := i - 1;
      while (t >= 0) and (s[i] - s[t] <= m) do
        begin
          if F[i] > F[t] + max[t + 1] then F[i] := F[t] + max[t + 1];
          k := prev[t];
          if (k >= 0) and (max[k + 1] < max[t + 1]) then max[k + 1] := max[t + 1];
          t := k;
        end;

      if F[i] = F[i - 1] then prev[i] := prev[i - 1] else prev[i] := i - 1;
    end;

  writeln(fo, F[n]);

  close(fo);
end;

begin
  init;
  solve;
end.

Code mẫu của khuc_tuan

#include "iostream"
#include "stdio.h"

using namespace std;

typedef long long LL;

#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)

const int maxn = 100010;

typedef LL mang[maxn];

struct Node {
    int c;
    LL Smin, Fmin;
};    

int n;
LL m, maxLL, result;
int a[maxn], tr[maxn];
mang Sum, F;
Node it[4*maxn];

void nhap() {
    scanf("%d%lld",&n,&m);
    For(i,1,n) scanf("%d",a+i);
}    

void init() {
    memset( &maxLL, 0x1f, sizeof(maxLL));
    For(i,1,4*n) {
        it[i].Smin = maxLL ;
        it[i].Fmin = maxLL ;
        it[i].c = -1 ;
    }    
    For(i,1,n) Sum[i] = Sum[i-1] + a[i];
    For(i,1,n) {
        int j = i-1;
        while( (j>0) && (a[j]<=a[i]) ) j = tr[j];
        tr[i] = j;
    }    
}    

void update_f(int node,int left,int right,int i,LL val,int cc) {
    if( cc==-1 && it[node].c!=-1 ) cc = it[node].c;
    if(left==right) {
        it[node].Fmin = val ;
        if(cc==-1) it[node].Smin = val ;
        else it[node].Smin = val + cc;
    }    
    else {
        int mid = (left+right)/2;
        if(i<=mid) update_f(2*node,left,mid,i,val,cc);
        else update_f(2*node+1,mid+1,right,i,val,cc);
        it[node].Fmin = min( it[2*node].Fmin, it[2*node+1].Fmin);
        if(cc==-1) it[node].Smin = min( it[2*node].Smin, it[2*node+1].Smin);
        else it[node].Smin = it[node].Fmin + cc;
    }    
}    

void update_c(int node,int left,int right,int st,int en,int c,int cc){
    if( cc==-1 && it[node].c!=-1 ) cc = it[node].c;
    if(st<=left && right<=en) {
        it[node].c = c;
        it[node].Smin = it[node].Fmin + c;
        return;
    }    
    int mid = (left+right)/2;
    it[node].c = -1 ;
    if(st<=mid) {
        update_c(2*node,left,mid,st,en,c,cc);
    }    
    else if(cc!=-1) {
        it[2*node].c = cc;
        it[2*node].Smin = it[2*node].Fmin + cc ;
    }    
    if(mid<en) {
        update_c(2*node+1,mid+1,right,st,en,c,cc);
    }
    else if(cc!=-1) {
        it[2*node+1].c = cc;
        it[2*node+1].Smin = it[2*node+1].Fmin + cc ;
    }        
    it[node].Smin = min(it[2*node].Smin,it[2*node+1].Smin);
}    

void findmin(int node,int left,int right,int st,int en,int cc) {
    if( cc==-1 && it[node].c!=-1 ) cc = it[node].c;
    if(st<=left && right<=en) {
        if(cc==-1) result = min(result,it[node].Smin);
        else result = min(result,it[node].Fmin+cc);
        return;
    }    
    int mid = (left+right)/2;
    if(st<=mid) findmin(2*node,left,mid,st,en,cc);
    if(mid<en) findmin(2*node+1,mid+1,right,st,en,cc);
}    

void dynamic() {
    int st=1, st_j;
    update_f(1,1,n,1,0,-1);
    For(i,1,n) {
        while(Sum[i]-Sum[st-1]>m) ++st;
        st_j = tr[i];
        if(st_j<st) update_c(1,1,n,st,i,a[i],-1);
        else update_c(1,1,n,st_j+1,i,a[i],-1);
        result = maxLL ;
        findmin(1,1,n,st,i,-1);
        F[i] = result;
        if(i<n) update_f(1,1,n,i+1,F[i],-1);
    }    
}    

void xuly() {
    For(i,1,n) if(a[i]>m) {
        printf("-1\n");
        return;
    }    
    init();
    dynamic();
    printf("%lld",F[n]);
}    

int main() {
    nhap();
    xuly();
//    system("pause");
    return 0;
}