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 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 oo = 1e9;
const int N = 100005;
using namespace std;

int MAX[N], MIN[N], val[N], a[N];
int n, k, d;

void maxi(int &a, int b) {a = a > b ? a : b;}
void mini(int &a, int b) {a = a > b ? b : a;}

void upd(bool t, int i, int v) {
    for(i++; i; i -= i & -i)
    if (t) maxi(MAX[i], v); else mini(MIN[i], v);
}

int get(bool t, int i) {
    int ret;
    if (t) {
        ret = -oo;
        for(i++; i <= d + 1; i += i & -i)
            maxi(ret, MAX[i]);
    }
    else {
        ret = oo;
        for(i++; i <= d + 1; i += i & -i)
            mini(ret, MIN[i]);
    }
    return ret;
}

bool ok(int lim) {
    REP(i, 1, d + 1) MIN[i] = oo, MAX[i] = -oo;
    int f0, f1;
    upd(0, a[0], 0); upd(1, a[0], 0);
    REP(i, 1, n) {
        int tmp = lower_bound(val + 1, val + 1 + d, val[a[i]] - lim) - val;
        f0 = get(0, tmp) + 1; f1 = get(1, tmp) + 1;
        upd(0, a[i], f0); upd(1, a[i], f1);
    }
    return f0 <= k && k <= f1;
}

II b[N];
int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    int mi = oo;
    REP(i, 1, n) {
        cin >> a[i];
        a[i] += a[i - 1];
        b[i] = MP(a[i], i);
    }
    sort(b, b + 1 + n);
    d = 0;
    REP(i, 0, n) {
        if (i == 0 || b[i].X != b[i - 1].X) d++;
        val[d] = a[b[i].Y]; a[b[i].Y] = d;
    }
    int l = -oo, r = oo, ans;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (ok(mid)) {
            ans = mid; r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung

//  Thuat toan: bai nay trong co ve kho tuy nhien neu nhin duoi goc do SD cau
//  truc du lieu, day la 1 bai kha binh thuong
//  * NX1: Neu ta chia duoc day so voi M0 thi voi moi M>=M0 ta deu chia duoc
//    => Chat nhi phan
//  * NX2: Voi moi gia tri M0, de kiem tra xem co the chia duoc ko, ta can
//    xac dinh gia tri kmin va kmax tuong ung la so doan nho nhat va lon nhat
//    co the chia duoc
//  * NX3: Tinh kmin va kmax don gian la bai toan quy hoach dong 1 chieu ket
//    hop voi cau truc du lieu thich hop de tim min/max trong doan

{$R-,Q-}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       15111*2;
  oo            =       500111000;
type
  BITree        =       object
        ln,nn   :       array[1..MAXN] of longint;
        procedure init;
        procedure updateMin(u,k:longint);
        procedure updateMax(u,k:longint);
        function getMin(u:longint):longint;
        function getMax(u:longint):longint;
  end;
var
  f1,f2         :       text;
  n,k,size      :       longint;
  a,sum         :       array[0..MAXN] of longint;
  si,sj         :       array[1..MAXN] of longint;
  c,ind         :       array[1..MAXN] of longint;
  bit           :       BITree;
  fl,fn         :       array[1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure BITree.init; inline;
    var
      i:longint;
    begin
      for i:=1 to size do
        begin
          ln[i]:=-oo;
          nn[i]:=oo;
        end;
    end;
procedure BITree.updateMin(u,k:longint); inline;
    var
      v:longint;
    begin
      nn[u]:=min(nn[u],k);
      v:=u+u and (-u);
      if v<=size then updateMin(v,k);
    end;
procedure BITree.updateMax(u,k:longint); inline;
    var
      v:longint;
    begin
      ln[u]:=max(ln[u],k);
      v:=u+u and (-u);
      if v<=size then updateMax(v,k);
    end;
function BITree.getMin(u:longint):longint; inline;
    var
      v,kq:longint;
    begin
      kq:=nn[u];
      v:=u-u and (-u);
      if v>0 then kq:=min(kq,getMin(v));
      exit(kq);
    end;
function BITree.getMax(u:longint):longint; inline;
    var
      v,kq:longint;
    begin
      kq:=ln[u];
      v:=u-u and (-u);
      if v>0 then kq:=max(kq,getMax(v));
      exit(kq);
    end;
procedure swap(var a,b:longint); inline;
    var
      temp:longint;
    begin
      temp:=a; a:=b; b:=temp;
    end;
procedure sort(l,r:longint); inline;
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=c[l+random(r-l+1)];
      repeat
        while c[i]>mid do inc(i);
        while c[j]<mid do dec(j);
        if i<=j then
          begin
            swap(c[i],c[j]);
            swap(ind[i],ind[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;
procedure RR(x:longint);
    var
      i,j:longint;
    begin
      j:=1; c[1]:=0; ind[1]:=0;
      for i:=1 to n do
        begin
          inc(j); c[j]:=sum[i];   ind[j]:=i;
          inc(j); c[j]:=sum[i]-x; ind[j]:=-i;
        end;
      sort(1,j);
      size:=1;
      if ind[1]>0 then si[ind[1]]:=1 else if ind[1]<0 then sj[-ind[1]]:=1;
      for i:=2 to j do
        begin
          if c[i]<c[size] then
            begin
              inc(size);
              c[size]:=c[i];
            end;
          if ind[i]>0 then si[ind[i]]:=size
          else if ind[i]<0 then sj[-ind[i]]:=size;
        end;
      bit.init;
      for i:=1 to size do
        if c[i]=0 then
          begin
            bit.updateMin(i,0);
            bit.updateMax(i,0);
            break;
          end;
    end;
function check(x:longint):boolean; inline;
    var
      i,u:longint;
    begin
      RR(x);
      for i:=1 to n do
        begin
          u:=bit.getMin(sj[i]);
          fn[i]:=u+1;
          bit.updateMin(si[i],u+1);

          u:=bit.getMax(sj[i]);
          fl[i]:=u+1;
          bit.updateMax(si[i],u+1);
        end;
      exit( (fn[n]<=k) and (k<=fl[n]) );
    end;
procedure solve;
    var
      l,r,mid,kq:longint;
    begin
      l:=-oo; r:=oo; kq:=0;
      repeat
        mid:=(l+r) div 2;
        if check(mid) then
          begin
            kq:=mid;
            r:=mid-1;
          end
        else l:=mid+1;
      until l>r;
      writeln(f2,kq);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,n,k);
      for i:=1 to n do
        read(f1,a[i]);
      for i:=1 to n do
        sum[i]:=sum[i-1]+a[i];
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của khuc_tuan

const
 fin = '';
 maxn= 16000 ;
type
  node = object
    min, max : longint ;
  end;
var
 fi : text ;
 n, k : longint ;
 ind, pos, a : array[0..maxn] of longint ;
 int : array[1..4*maxn] of node ;
procedure nhap;
 var
  i : longint ;
 begin
   read( fi, n, k);
   a[0] := 0;
   for i:=1 to n do
    begin
      read( fi, a[i]);
      a[i] := a[i-1] + a[i] ;
    end;
 end;
procedure sort( l, r : longint );
 var
  i, j : longint ;
  t, x : longint ;
 begin
     i := l;
     j := r;
     x := a[ind[(l+r) div 2]];
     repeat
       while a[ind[i]]<x do inc(i);
       while a[ind[j]]>x do dec(j);
       if i<=j then
        begin
          t := ind[i]; ind[i] := ind[j]; ind[j] := t;
          inc(i); dec(j);
        end;
     until i>j;
     if i<r then sort( i, r);
     if l<j then sort( l, j);
 end;
procedure init;
 var
  i : longint ;
 begin
   for i:=0 to n do ind[i] := i;
   sort( 0, n);
   for i:=0 to n do pos[ind[i]] := i;
 end;
procedure prepare;
 var
  i : longint ;
 begin
   for i:=1 to 4*n do
     begin
       int[i].min := 1000000000 ;
       int[i].max :=-1000000000 ;
     end;
 end;
procedure update( node, left, right, i, value : longint );
 var
  mid : longint ;
 begin
   with int[node] do
    begin
      if min>value then min := value ;
      if max<value then max := value ;
    end;
   if left<right then
     begin
       mid := (left+right) div 2;
       if i<=mid then update( 2*node, left, mid, i, value )
       else update( 2*node +1 , mid+1, right, i, value );
     end;
 end;
function find( x : longint ) : longint ;
 var
  left, right, mid : longint ;
 begin
   left := 0;
   right := n ;
   if a[ind[n]]<x then exit(-1);
   while left<right do
    begin
      mid := (left+right) div 2;
      if a[ind[mid]]>=x then right := mid
      else left := mid+1;
    end;
   find := left ;
 end;
procedure down( var a : longint; b : longint );
 begin
   if a>b then a := b;
 end;
procedure up( var a : longint ; b : longint );
 begin
   if a<b then a := b;
 end;
function getmin( node, left, right, x, y : longint ) : longint ;
 var
  mid, r : longint ;
 begin
   if (x<=left) and (right<=y) then exit( int[node].min );
   mid := (left+right) div 2;
   r := 1000000000 ;
   if x<=mid then down( r, getmin( 2*node, left, mid, x, y));
   if mid<y then down( r, getmin( 2*node+1, mid+1, right, x, y));
   getmin := r;
 end;
function getmax( node, left, right, x, y : longint ) : longint ;
 var
  mid, r : longint ;
 begin
   if (x<=left) and (right<=y) then exit( int[node].max );
   mid := (left+right) div 2;
   r := -1000000000;
   if x<=mid then up( r, getmax( 2*node, left, mid, x, y));
   if mid<y then up( r, getmax( 2*node+1, mid+1, right, x, y));
   getmax := r ;
 end;
function testok( x : longint ) : boolean ;
 var
  min, max, left, i : longint ;
 begin
    prepare;
    update( 1, 0, n, pos[0], 0);
    for i:=1 to n do
     begin
        left := find( a[i] - x);
        if left<>-1 then
         begin
           min := getmin( 1, 0, n, left, n)+1;
           max := getmax( 1, 0, n, left, n)+1;
           if i=n then exit((min<=k) and (k<=max));
           if min<=max then
            begin
               update( 1, 0, n, pos[i], min);
               update( 1, 0, n, pos[i], max);
            end;
         end;
     end;
    testok := false;
 end;
procedure xuly;
 var
  left, right, mid : longint ;
 begin
   init;
   left := -1000000000;
   right:=  1000000000;
   while left<right do
    begin
      if left+1=right then mid := left else mid := (left+right) div 2;
      if testok(mid) then right := mid else left := mid + 1;
    end;
   writeln( left );
 end;
procedure main;
 var
  st, i : smallint ;
 begin
   //read( fi, st);
   st := 1;
   for i:=1 to st do
    begin
      nhap;
      xuly;
    end;
 end;
begin
  assign( fi, fin); reset( fi);
    main;
  close( fi);
end.