LABUDOVI – spoj

Đề bài:

Thuật toán:

  • BFS
  • Bài này chú ý dùng phương pháp loang đồ thị để làm; chúng ta sẽ dùng 2 mảng nextx, nexty để loang ra 4 ô xung quanh của 1 ô.
  • Đầu tiên đánh dấu vị trí của 2 con thiên nga và đánh dấu tất cả các ô là nước.
  • Sau đó tiến hành loang từ con thiên nga thứ nhất. Nếu gặp con thiên nga thứ hai thì return.
    Nếu không thì tiến hành loang các ô bên cạnh là ô băng; nếu gặp ô băng thì chuyển thành ô nước, đánh dấu lại và tăng biến đếm lên 1. Tiếp tục như vậy cho tới khi gặp được con thiên nga thứ hai.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
 
    cout << endl;
    FOR(i, 1, m)
    {
        FOR(j, 1, n)
        {
            cout << Time[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
 
 
}
 
 
void Enter()
{
	int cnt = 1;
	MEMS(Free, true);
 
 
	scanf("%d%d", &m, &n);
 
 
 
 
	FOR(i, 1, m)
	{
	    FOR(j, 1, n)
	    {
 
	        cin >> a[i][j];
 
 
            if(a[i][j] != 'X')
            {
                Time[i][j] = 0;
 
                mainq.push(ii(i, j));
 
                if(a[i][j] == 'L')
                {
                    start[cnt] = ii(i, j);
                    ++cnt;
                }
 
                Free[i][j] = false;
            }
            else Time[i][j] = 1234567890;
 
            ++nInstruction;
 
 
	    }
	}
 
}
 
//Check
bool IsValid(int _x, int _y)
{
    return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
 
void PreProcess()
{
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        ++nInstruction;
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
 
            if(IsValid(x, y))
            {
                if(a[x][y] == 'X')
                {
                    Free[x][y] = false;
                    mainq.push(ii(x, y));
                    Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
                }
            }
        }
 
    }
 
    //Debug();
 
 
 
}
void FloodFill1(ii st1, ii st2)
{
    mainq.push(st1);
    Free[st1.first][st1.second] = false;
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        //Time[curx][cury] = nTime;
        ++nInstruction;
 
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
            ii dir = ii(x, y);
 
            if(IsValid(x, y))
            {
                Free[x][y] = false;
                if(dir == st2) return;
                if(Time[x][y] <= res) mainq.push(dir);
                else subq.push(dir);
            }
        }
 
        if(mainq.empty())
        {
            ++res;
            swap(mainq, subq);
        }
 
    }
}
 
//Process
void Solve()
{
    res = 0;
    PreProcess();
    MEMS(Free, true);
    FloodFill1(start[1], start[2]);
    printf("%d", res);
 
 
    cerr << endl;
    cerr << nInstruction << endl;
 
}
 
//Main Procedure
int main()
{
    Enter();
    Solve();
    return 0;
}

VOTREE – spoj

Đề bài:

Giải thích ví dụ

votree-yeulaptrinh
Truy vấn 1: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 2 đến 5, ở đây có thể thấy 2 là tổ tiên chung gần nhất của các đỉnh 2,3,4,5.
Truy vấn 2: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 1 đến 3, ở đây có thể thấy 1 là tổ tiên chung gần nhất của các đỉnh 1,2,3.
Truy vấn 3: Tìm tổ tiên chung gần nhất của các đỉnh được đánh số từ 4 đến 5, ở đây có thể thấy 3 là tổ tiên chung gần nhất của các đỉnh 4,5.

Thuật toán:

    Có thể nhận thấy rằng tổ tiên chung gần nhất ( LCA ) của 3 đỉnh a,b,c sẽ bằng với LCA(a,LCA(c,b)). Dựa trên tính chất nãy ta có thể sử dụng Interval Tree để tìm LCA của 1 đoạn liên tiếp bằng cách tổ chức cây IT sẽ lưu LCA của các phần tử trong đoạn quản lý.

    Các phần cơ bản của cây IT:

    IT[id] = phần tử đang được quản lý khi đoạn quản lý gồm 1 phần tử.

    IT[id] = LCA(IT[id*2],IT[id*2+1] ).

    P/s : Có rất nhiều cách để tìm LCA ví dụ như : Sparse Table, Heavy Light Decomposition, Interval Tree, …

Code:

const
        tfi='';
        tfo='';
 
var
        fi,fo:Text;
        ke,nx:array[-70000..70000] of longint;
        num,thoat,hd:array[0..70000] of longint;
        f:array[0..70000,0..20] of longint;
        n,q,jmax,dem,dem1:longint;
        t:array[0..3000000] of longint;
 
procedure nhap;
        var i,j,u,v:longint;
        begin
                read(fi,n,q);
                for i:=1 to n-1 do
                        begin
                                read(fi,u,v);
                                ke[i]:=v;
                                nx[i]:=hd[u];
                                hd[u]:=i;
                                ke[-i]:=u;
                                nx[-i]:=hd[v];
                                hd[v]:=-i;
                        end;
                for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
        end;
 
procedure DFS(u:longint);
        var j,v:longint;
        begin
                inc(dem);
                num[u]:=dem;
                for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
                j:=hd[u];
                while j<>0 do
                        begin
                                v:=ke[j];
                                if f[v,0]=0 then
                                        begin
                                                f[v,0]:=u;
                                                DFS(v);
                                        end;
                                j:=nx[j];
                        end;
                inc(dem1);
                thoat[u]:=dem1;
        end;
 
function cha(x,y:longint):boolean;
        begin
            cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
        end;
 
function lca(x,y:longint):longint;
        var j:longint;
        begin
                if cha(x,y) then exit(x);
                if cha(y,x) then exit(y);
                for j:=jmax downto 0 do
                        if not cha(f[x,j],y) then x:=f[x,j];
                exit(f[x,0]);
        end;
 
procedure init(i,l,r:longint);
        var mid:longint;
        begin
            if l=r then
                begin
                        t[i]:=l;
                        exit;
                end;
            mid:=(l+r) div 2;
            init(i*2,l,mid);
            init(i*2+1,mid+1,r);
            t[i]:=lca(t[i*2],t[i*2+1]);
        end;
 
function get(i,l,r,u,v:longint):longint;
        var mid:longint;
        begin
                if (l>v) or (r<u) then exit(u);
                if (u<=l) and (r<=v) then exit(t[i]);
                mid:=(l+r) div 2;
                get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
        end;
 
procedure xuli;
        var i,u,v,pa,j:longint;
        begin
                f[1,0]:=1;
                DFS(1);
                init(1,1,n);
                for i:=1 to q do
                        begin
                                read(fi,u,v);
                                writeln(fo,get(1,1,n,u,v));
                        end;
 
        end;
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(fi);
        rewrite(fo);
        nhap;
        xuli;
        close(fo);
end.

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

INFORMAC – spoj

Đề bài:

Thuật toán:

Code:

uses math;
const
  fi='';//informac.inp';
  fo='';//informac.out';
  maxm=40000;
  maxn=200;
var
  match : array[1..maxn] of longint;
  l,r : array[1..maxn] of longint;
  left,right  :  array[1..maxn] of longint;
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,x,y,u,v : longint;
  kt : boolean;
procedure enter;
  var i,j,k : longint;
  begin
    assign(input,fi);reset(input);
    read(n,m);
    for i:=1 to n do
      begin
        r[i] := n;
        right[i] := n;
      end;
    for i:=1 to n do
      begin
        l[i] := 1;
        left[i] := 1;
      end;
    for i:=1 to m do
      begin
        read(j,x,y,v);
        left[v] := max(left[v], x);
        right[v] := min(right[v], y);
        if j = 1 then
          begin
            for k := x to y do r[k] := min(r[k],v);
          end;
        if j = 2 then
          begin
            for k := x to y do l[k] := max(l[k],v);
          end;
      end;
    close(input);
  end;
Procedure Ghepcap;
  var old,i,j,nlist : longint;
      cx : array[1..maxn] of boolean;
      found : boolean;
      list : array[1..maxn] of longint;
  procedure dfs( u : longint);
    var v,i : longint;
    begin
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if cx[v] then
            begin
              cx[v] := false;
              if match[v] = 0 then found := true else dfs(match[v]);
              if found then
                begin
                  match[v] := u;
                  exit;
                end;
            end;
          i := link[i];
        end;
    end;
  begin
    for i:=1 to n do list[i] := i;
    nlist := n;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until nlist = old;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure process;
  begin
    kt := false;
    for i:=1 to n do
      if r[i] < l[i] then exit;
    for i:=1 to n do
      for j:=left[i] to right[i] do
        if (i>=l[j]) and (i<=r[j]) then
        begin
          inc(m);
          add(m,i,j);
        end;
    ghepcap;
    for i:=1 to n do
      if match[i] = 0 then exit;
    kt := true;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    if not kt then writeln(-1) else for i:=1 to n do write(match[i],' ');
  end;
begin
  enter;
  process;
  print;
end.

SAFENET2 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const
  fi='';//safenet.inp';
  fo='';//safenet.out';
  maxn=50000;
  maxm=200000;
  oo=trunc(1e9);
type
  Tedge = record
     x,y  : longint;
     end;
var
  link,head,ke : array[-maxm..maxm] of longint;
  i,j,n,m,u,v,ans,top,count,dem : longint;
  num,low : array[1..maxn] of longint;
  st : array[1..maxm] of Tedge;
  free : array[-maxm..maxm] of boolean;
  pa : array[1..maxn] of longint;
procedure push(x,y : longint);
  begin
    inc(top);
    st[top].x := x;
    st[top].y := y;
  end;
procedure pop ( var x,y : longint);
  begin
    x := st[top].x;
    y := st[top].y;
    dec(top);
  end;
procedure dfs(u : longint);
  var i,v,x,y : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := oo;
    if count = 1 then
      if head[u] = 0 then
        ans := max(ans,1);
    i := head[u];
    while i <> 0 do
      begin
          v := ke[i];
          if v <> pa[u] then
          if num[v] = 0 then
            begin
              pa[v] := u;
              push(u,v);
              dfs(v);
              low[u] := min(low[u],low[v]);
              if low[v] >= num[u] then
                begin
                  dem := 0;
                  repeat
                    pop(x,y);
                    dem := dem + 1;
                  until (X=U) AND (Y=V);
                  ans := max(ans,dem+1);
                end;
            end
            else
            begin
              low[u] := min(low[u],num[v]);
            end;
        i := link[i];
      end;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure main;
var i  :  longint;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  read(n,m);
  for i := 1to m do
    begin
      read(u,v);
      add(i,u,v);
      add(-i,v,u);
    end;
  fillchar(free,sizeof(free),true);
  for i := 1 to n do
    if num[i] = 0 then
      begin
        count := 0;
        dfs(i);
      end;
  writeln(ans);
  close(input);close(output);
end;
begin
  main;
end.

QBAGENTS – spoj

Đề bài:

Thuật toán:

  • BFS

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        maxm=maxn*maxn;
        oo=trunc(1e9);
type    Tq      =record
                u1,u2,k :longint;
                end;
var     q       :array[1..2*maxn*maxn*10] of Tq;
        cx      :array[1..maxn,1..maxn,1..2] of boolean;
        f       :array[1..maxn,1..maxn,1..2] of longint;
        i,j,n,m,s,t     :longint;
        dau,cuoi,res    :longint;
        // danh sach
        link,head,ke    :array[1..maxm] of longint;
procedure enter;
var     u,v     :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m,s,t);
        for i:=1 to m do
                begin
                        read(u,v);
                        link[i] := head[u];
                        head[u] :=i;
                        ke[i] := v;
                end;
        close(input);
end;
procedure push(x,y,z:longint);
begin
        inc(cuoi);
        q[cuoi].u1:=x;
        q[cuoi].u2:=y;
        q[cuoi].k:=z;
end;
procedure process;
var     v1,v2,u1,u2,k :longint;
begin
        dau :=1; cuoi :=0;
        push(s,t,1);
        fillchar(cx,sizeof(cx),true);
        //
        for i:=1 to n do
                for j:=1 to n do
                        for k:=1 to 2 do
                                f[i,j,k] := oo;
        f[s,t,1] := 0;
        while dau<=cuoi do
                begin
                        u1 := q[dau].u1;
                        u2 := q[dau].u2;
                        k := q[dau].k;
                        inc (dau);
                        if k=1 then
                                begin
                                        i := head[u1];
                                        while i>0 do
                                                begin
                                                        v1 := ke[i];
                                                        if cx[v1,u2,2] then
                                                          begin
                                                                f[v1,u2,2] := min(f[v1,u2,2],f[u1,u2,1]+1);
                                                                push(v1,u2,2);
                                                                cx[v1,u2,2] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                        if k=2 then
                                begin
                                        i := head[u2];
                                        while i>0 do
                                                begin
                                                        v2 := ke[i];
                                                        if cx[u1,v2,1] then
                                                          begin
                                                                f[u1,v2,1] := min(f[u1,u2,2]+1,f[u1,v2,1]);
                                                                push(u1,v2,1);
                                                                cx[u1,v2,1] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                end;
        res := oo;
        for i:=1 to n do
                res := min(res,f[i,i,1]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        if res=oo then write(-1) else write(res div 2);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

TRAKA – spoj

Đề bài:

Tóm tắt đề

Có N người thợ, M chiếc xe. Người thứ i hoàn thành việc sửa bộ phận xe mình phụ trách với tốc độ T[i]. Xe thứ j có độ rắc rối là F[j]. Thời gian người thứ i cửa xong bộ phận người i phụ trách trên xe j trong thời gian T[i] * F[j]. Các công việc được thực hiện theo thứ tự từ người 1 -> n. Người i làm việc liên tục ko đc dừng lại(tức là sửa xong xe i thì đến xe i + 1). Với mỗi thời điểm t, mỗi chiếc xe chỉ được sửa bởi tối đa 1 người. Tính thời điểm bé nhất để n người sửa xong m chiếc xe.

Dữ Liệu:

  • Dòng đầu gồm 2 số nguyên N (1 <= N <= 100 000) – số người thợ, M (1 <= M <= 100 000) – số chiếc xe cần sửa.
  • Dòng thứ i trong n dòng tiếp theo là T[i] – tốc độ sửa xong bộ phận người i phụ trách.
  • Dòng thứ j trong m dòng tiếp theo là F[j] – độ rắc rối của chiếc xe thứ j.

Kết quả:

  • Gồm 1 dòng là kết quả của bài toán.

Ví dụ:

Input:

3 3
2
1
1
2
1
1

Output:

11

Thuật toán:

Ở bài toán này thì thời điểm kết thúc công việc của người n là kết quả bài toán. Vì mỗi người thợ sẽ làm việc liên tục ko nghỉ nên ta cần tìm thời điểm bắt đầu thực hiện công việc của người n.
Gọi q[i] là tổng độ phức tạp của các chiếc xe từ 1 -> i.

Xét:
Người thứ u bắt đầu công việc từ thời điểm 0, tốc độ C. Thời điểm người u hoàn thành xe i là q[i] * C, hoàn thành xe i + 1 là q[i + 1] * c.
Người thứ v bắt đầu công việc ngay sau u, tốc độ D. Có thời điểm hoàn thành xe i là q[i] * D.
=> Để người v sửa xe i + 1 thì v cần chờ 1 khoảng thời gian là q[i + 1] * C – q[i] * D. Ta cần tìm min(q[i + 1] * C – q[i] * D).
Từ đây, ta để tính được thời điểm bắt đầu làm việc của người n là delta.
Kết quả bài toán là: delta + q[m] * t[n].

Nhận thấy độ phức tạp của thuật toán trâu bò là O(n * m) không đem lại thuật toán đủ tốt để giải bài toán. Nên ta cần tìm cách giảm độ phức tạp xuống.

Vậy, chúng ta nên làm thế nào ?? 😀 ??

Nhìn vào biểu thức q[i + 1] * C – q[i] * D có j đặc biệt ? Đây là biểu thức tích chéo của 2 vector (C; D) * (q[i]; q[i + 1]).

Coi (q[i]; q[i + 1]) là 1 điểm trên mặt phẳng tọa độ Oxy, và ta có vector u = (C; D).
Ta cần tìm điểm A(x, y) sao cho vector OA * u bé nhất. Nhận thấy điểm A cần tìm nằm trên đường lồi.

Trong hình vẽ bên dưới, đường thẳng màu xanh là đường lồi.

traka-yeulaptrinh.pw

Nhận thấy, các điểm trên đường lồi có tích chéo với (C; D) có giá trị theo hình parabol. Đến đây ta có thể áp dụng kĩ thuật chặt nhị phân hoặc tam phân để tìm đỉnh có tích chéo bé nhất.

Độ phức tạp là: O(m * log(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <long long, long long> ii;
 
const int N = 1e5 + 10;
 
int n, m, k;
ii A[N], p[N];
long long t[N];
 
ii operator - (ii a, ii b) { return  make_pair(b.first - a.first, b.second - a.second); }
long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
 
bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
 
void load() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        A[i] = make_pair(t[i - 1], t[i]);
}
 
void findConvexLine() {
    k = 0;
    p[k++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
        p[k++] = A[i];
    }
}
 
long long get(int x, int y) {
    //ii v = make_pair(x, y);
    int l = 0, r = k - 2, cur = 0;
    while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
        int mid = (l + r) >> 1;
        if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
            l = mid + 1;
            cur = l;
        } else {
            r = mid - 1;
        }
    }
    return make_pair(x, y) * p[cur];
}
 
void process() {
    findConvexLine();
    int x = 0, y = 0;
    long long delay = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &y);
        delay += get(x, y);
      //  cerr << get(x, y) << "\n";
        x = y;
    }
    long long ans = delay + 1ll * t[n] * x;
    printf("%lld\n", ans);
}
 
int main() {
 
    load();
    process();
 
    return 0;
}