SPOJ

QBMARKET – SPOJ

June 15, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/QBMARKET/

Thuật toán:

Gọi L[j] là số cách mua hàng khi có j đồng .Như vậy khi ta có khi ta mua các mặt hàng từ (1..i-1) hết j đồng và số cách mua là L[j] thì khi xét đến mặt hàng thứ i với k là số lượng mặt hàng i mà ta sẽ mua thì số cách mua hết j+c[i]*k ( S) đồng sẽ tăng thêm một lượng L[j]. Ta có công thức quy hoạch động :

Nếu j+c[i]*k<=S thì L[j+c[i]*k]:=L[j+c[i]*k]+L[j] (j=S..1,i=1..n,k=1..m_i). Khởi tạo L[0]=1, L[1..S]=0.

Tại sao vì j+c[i]*k<=S vì nếu lớn hơn S rồi ta không cần quan tâm vì ta chỉ có tối đa S đồng thôi.

Trong qua trình cài đặt ta thấy nếu ta duyệt nếu ta duyệt j tăng dần từ 1 đến S, k tăng dần từ 1 đến m_i thì sẽ xảy ra trường hợp như sau:j=0,L[0]=1,i=1,c[1]=1. Đầu tiên k=1 thì L[0+1*1]=L[0]+L[2]=1, k=2 thì L[0+1*2]=L[0]+L[2]=1.
Tăng j và i giữ nguyên, j=1.Đầu tiên k=1 thì L[1+1*1]=L[1]+L[1]=2 đến đây ta đã thấy vô lí L[2] với i=1 không thể nào bằng 2 được mà L[2]=1. Trường hợp này là do khi j=j₁ ta tính L[j₁+x], j tăng lên j₁+x ta tính L[j₁+x+y] ta có

L[j₁+x+y]=L[j₁+x+y]+L[j₁+x] mà khi đó L[j₁+x] không còn là số cách mua hết j1+x đồng từ i-1 mặt hàng (1..i-1) mà là mua i mặt hàng (1..i) vì ta vừa tính L[j₁+x] khi mua k mặt hàng i mà c[i]*k=x, tất nhiên k>=1.Nói ngắn gọn bạn phải hiểu L[j] trong công thức trên là số cách mua hết j đồng từ i-1 mặt hàng (1..i-1)

Để khắc phục tình trạng này ta duyệt j giảm từ S về 0 .

Code bên dưới nộp sẽ được 85 điểm do chạy quá thời gian. Nếu bài cho time limit 1s thì sẽ được 100 điểm. Tất nhiên thuật toán trên hoàn toàn đúng.

Code:

Const
        fi='';
        fo='';
        maxn=500;
        maxs=100000;

Type
        arr1    =array[1..maxn] of longint;
        arr2    =array[0..maxs] of int64;

Var
        n,s     :longint;
        c,m     :arr1;
        L       :arr2;
        f       :text;

procedure nhap;
var
        i       :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,s,n);
        for i:=1 to n do readln(f,c[i],m[i]);
        close(f);
end;

procedure solution;
var
        i,j,k   :longint;
begin
        L[0]:=1; {Neu co 0 dong thi coi la co mot cach la khong mua gi ca}
        for j:=1 to s do L[j]:=0; { Khoi tao mang L }
        for i:=1 to n do
                for j:=s downto 0 do
                        if L[j]>0 then
                        	for k:=1 to m[i] do
                                if j+k*c[i]<=s then
                                        L[j+c[i]*k]:=L[j]+L[j+c[i]*k];
end;

procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,L[s]); {Ket qua nam o L[s]}
        close(f);
end;

begin
        nhap;
        solution;
        xuat;
end.

Chủ đề: Quy hoạch động, SPOJ Mức độ: QHĐ

MMOD29 – SPOJ

June 15, 2016 by Aida Nana 2 Comments

Đề bài: http://vn.spoj.com/problems/MMOD29/

Thuật toán:

(đang cập nhập)

Code:

const   fi      ='';
        fo      ='';

var     f1, f2       :text;
        x       :longint;
        a, b, c :longint;
function get(a, b:longint):longint;
var     tmp     :longint;
begin
        if b = 0 then exit(1);
        if b mod 2 = 0 then exit(sqr(get(a, b div 2)) mod 29 )
        else exit( (sqr(get(a, b div 2))*a) mod 29 );
end;

BEGIN
        assign(f1, fi);
        reset(f1);
        assign(f2, fo);
        rewrite(f2);
        while not eof(f1) do
                begin
                        readln(f1, x);
                        if x = 0 then break;
                        a:=(get(2, 2*x + 1) - 1 ) mod 29;
                        b:=(get(3,   x + 1) - 1 ) mod 29;
                        c:=(get(167, x + 1) - 1 ) mod 29;
                        writeln(f2,(a*b*c*9) mod 29);
                end;
        close(f1);
        close(f2);
END.

Chủ đề: SPOJ

QBROBOT – SPOJ

June 10, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/QBROBOT/

Thuật toán:

Tìm đường đi ngắn nhất bằng Dijkstra
Chắt nhị phân giá trị w
Với mỗi giá trị w kiểm tra xem có thỏa mãn không

Code:

#include 
#include 
#include 
#include 
#define MAXN 502
#define MAXM 30002
#define VC 2000000000
int n, m, dau[MAXM], cuoi[MAXM], t[MAXM], c[MAXM], x[MAXN];
long tro[MAXN];
int ke[2*MAXM];
int qn, q[MAXN], vt[MAXN];
long kc[MAXN], nl[MAXN], ds;
int prev[MAXN];
int tt[MAXN], sl=0;
using namespace std;
int doc()
{
    int i;
    cin >> n;
    for (i=1; i<=n; i++) cin >> x[i];
    cin >> m;
    for (i=1; i<=m; i++) cin >> dau[i] >> cuoi[i] >> t[i] >> c[i];
}

// Ham dung do thi
int dungdt()
{
    long u,v;
    int i;
    for (i=1; i<=m; i++) {tro[dau[i]]++; tro[cuoi[i]]++;}
    for (v=0,i=1; i<=n; i++) {u=tro[i]; tro[i]=v+1; v+=u;}
    tro[n+1]=v+1;
    for (i=1; i<=m; i++) {ke[tro[dau[i]]++]=i; ke[tro[cuoi[i]]++]=i;}
    for (i=n; i>=2; i--) tro[i]=tro[i-1]; tro[1]=1;
}

// Cac ham quan ly hang doi uu tien
int up(int k)
{
    int v=q[k];
    while (kc[q[k/2]]>kc[v])
    {
        q[k]=q[k/2];
        vt[q[k]]=k;
        k/=2;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int down(int k)
{
    int v=q[k];
    while (2*k<=qn)
    {
        int l=2*k;
        if ((lkc[u]+t[ke[i]]))
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                update(v);
            }
            if (prev[v]==0)
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                put(v);
            }
        }
    }
    return 0;
}


// Ham kiem tra co di duoc hay khong
int diduoc(long w)
{
    long i,k,u,v,tg,cp,cl;
    for (i=1; i<=n; i++) nl[i]=-VC;
    nl[1]=w;
    for (k=1; k<=sl; k++)
    {
        u=tt[k];
        if (nl[u]>=0)
        for (i=tro[u]; i=cp))
            {
                cl=(x[v]==1) ? w : nl[u]-cp;
                if (cl>nl[v]) nl[v]=cl;
            }
        }
    }
    return (nl[n]>=0);
}

// Ham tim chi phi be nhat (dua vao theo tim kiem nhi phan)
int solve()
{
    long first=0, last=1, lim;
    while (!diduoc(last)) {first=last; last*=2;}
    while (last-first>1)
    {
        lim=(last+first)/2;
        if (diduoc(lim)) last=lim; else first=lim;
    }
    ds=last;
}

// Ham in ket qua
int viet()
{
    cout << ds;
    //<< // '\n';
    /*out << kc[n] << '\n';
    for (long i=tro[1]; i

Chủ đề: Dijkstra, SPOJ, Tìm kiếm nhị phân Mức độ: dijkstra, tknp

CATALAN – SPOJ

June 9, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/CATALAN/

Thuật toán:

Bài này sử dụng phương pháp đệ quy có nhớ. Bạn có thể đọc code để hiểu thêm

Code:

const
  fi='';
  fo='';
  maxn=21;
var
  f : array[1..2*maxn,0..2*maxn] of int64;
  i,j,n : longint;
  x,kq2 : array[1..2*maxn] of longint;
  res,kq1,k : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to 2*n+1 do read(x[i]);
    readln(k);
    close(input);
  end;
function tinh(i,tr : longint) : int64;
  var sl : int64;
  begin
    if f[i,tr]>-1 then exit(f[i,tr]);
    if i>2*n+1 then
      if tr=0 then exit(1) else exit(0);
    sl := 0;
    sl := sl + tinh(i+1,tr+1);
    if tr>0 then
    sl := sl + tinh(i+1,tr-1);
    f[i,tr] := sl;
    exit(sl);
  end;
procedure truyvan1;
  begin
    kq1 := 0;
    for i:=2 to 2*n do
      if x[i]>x[i-1] then
        if x[i]-2>=0 then
          kq1 := kq1 + tinh(i+1,x[i]-2);
    inc(kq1);
  end;
procedure lankq(i : longint);
  begin
    if i>2*n then exit;
    if kq2[i-1]-1>=0 then
      begin
        if k>tinh(i+1,kq2[i-1]-1) then
          begin
            k:=k-tinh(i+1,kq2[i-1]-1);
            kq2[i] := kq2[i-1]+1;
            lankq(i+1);
            exit;
          end;
      end
      else
        begin
          kq2[i] := kq2[i-1]+1;
          lankq(i+1);
          exit;
        end;
    kq2[i] := kq2[i-1]-1;
    lankq(i+1);
  end;
procedure truyvan2;
  begin
    kq2[1] := 0;
    lankq(2);
  end;
procedure process;
  begin
    fillchar(f,sizeof(f),255);
    res := tinh(2,0);
    f[1,0] := res;
    truyvan1;
    truyvan2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    //writeln(res);
    writeln(kq1);
    for i:=1 to 2*n+1 do write(kq2[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ

MINCUT – SPOJ

June 4, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/MINCUT/

Thuật toán:

Với mỗi cách cắt ngang, cắt dọc. Ta chặt nhị phân tìm nhát cắt sao cho độ chênh lệch 2 phần nhỏ nhất.
Chú ý với mỗi cách cắt ta phải chặt nhị phân 2 lần: value >= trunggian và value <= trunggian
Các bạn có thể đọc code để hiểu rõ hơn

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e3)+3;
        oo=trunc(1e15);
type    data=record
                x,y,u,v:longint;
                end;
var     m,n,i,j,k:longint;
        s:array[0..maxn,0..maxn] of int64;
        a:array[1..maxn,1..maxn] of longint;
        q:array[1..maxn*maxn] of data;
        res     :int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n,k);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    for i:=1 to k do
        with q[i] do
                read(x,y,u,v);
    close(input);
end;
procedure init;
begin
    for i:=1 to m do
        for j:=1 to n do s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
end;
function tinh(x,y,u,v:longint):int64;
begin
        exit(s[u,v]+s[x-1,y-1]-s[x-1,v]-s[u,y-1]);
end;
procedure solve;
var     tam,tam2        :int64;
        d,c,g   :longint;
begin
assign(output,fo);rewrite(output);
    for i:=1 to k do
      with q[i] do
        begin
            tam:=tinh(x,y,u,v);
            tam2 := tam div 2;
            res := oo;
            // cat hang
            d :=x; c:=u-1;
            g := (d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,g,v)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,g,v));
                        end;
            d:=x; c:=u-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,g,v)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,g,v)-tam);
                        end;
            // cat cot;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,u,g)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,u,g));
                        end;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,u,g)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,u,g)-tam);
                        end;
            writeln(res);
        end;
end;
begin
    nhap;
    init;
    solve;
end.

Chủ đề: SPOJ, Tìm kiếm nhị phân Mức độ: MINCUT spoj

VMKEY – SPOJ

May 24, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/VMKEY/

Thuật toán:

(đang cập nhập)

Code:

#include 
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;

using namespace std;
int d[100][100];
int w[100][100];
string s;
typedef pair ii;
int x[101];
ii p[110];
vector< ii > v;
int pos[11];
int dist[100][100];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vao.inp", "r", stdin);
    freopen("ra.out", "w", stdout);
    #endif //MIKELHPDATKE
   // cout<<"wtf"<> s;
    //cout<

Chủ đề: SPOJ Mức độ: VMKEY - spoj

NKCITY – SPOJ

May 24, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/NKCITY/

Thuật toán:

Giải bài này có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal đều được.
Các bạn có thể tham khảo cả 2 cách làm ở bên dưới.

Code:

Kruskal

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
        maxm    =10000;

type    data    =record
                u, v, c :longint;
                end;

var     f       :Text;
        n, m    :longint;
        Edges   :array[1..maxm] of Data;
        b       :Array[1..maxm] of longint;
        Father  :Array[1..maxn] of longint;
        res     :longint;
procedure nhap;
var     i, u, v, c :longint;
begin
        assign(f, fi);
        reset(f);
        readln(f, n, m);
        for i:=1 to m do
                begin
                        readln(f, u, v, c);
                        Edges[i].u:=u;
                        Edges[i].v:=v;
                        Edges[i].c:=c;
                end;
        close(f);
end;

Procedure init;
var     i :longint;
begin
        for i:=1 to m do b[i]:=i;
        for i:=1 to n do father[i]:=-1;
        res:=-1;
end;

procedure QS(l,r:longint);
var     i, j, x, tg     :longint;
begin
        i:=l;
        j:=r;
        x:=edges[b[ (l+r) div 2] ].c;
        repeat
                while Edges[b[i]].c < x do inc(i);
                while Edges[b[j]].c > x do dec(j);
                if i<=j then
                        begin
                                tg:=b[i];
                                b[i]:=b[j];
                                b[j]:=tg;
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l0 do t:=father[t];
        exit(t);
end;

procedure union(i, j:longint);
var     x :longint;
begin
        x:=father[i]+father[j];
        if father[i]>father[j] then
                begin
                        father[i]:=j;
                        father[j]:=x;
                end
        else    begin
                        father[j]:=i;
                        father[i]:=x;
                end;
end;

procedure Kruskal;
var     i, u,v, c, r1, r2 :longint;
begin
        init;
        QS(1,m);
        for i:=1 to m do
                begin
                        u:=Edges[b[i]].u;
                        v:=Edges[b[i]].v;
                        c:=Edges[b[i]].c;
                        r1:=find(u);
                        r2:=find(v);
                        if r1<>r2 then
                                begin
                                        union(r1,r2);
                                        res:=max(res,c);
                                end;
                end;
end;

procedure xuat;
begin
        assign(f, fo);
        rewrite(f);
        writeln(f, res);
        close(f);
end;

BEGIN
        nhap;
        Kruskal;
        xuat;
END.

Prim

const   fi='';
        fo='';
        maxn=1000;
        maxc=trunc(1e9);
var     d:array[1..maxn] of longint;
        i,j,n,m,res:longint;
        u,v,t:longint;
        cx:array[1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of longint;
procedure init;
begin
    for i:=1 to n do d[i]:=maxc;
    d[1]:=0;
    fillchar(cx,sizeof(cx),true);
end;
procedure prim;
var     min,u:longint;
begin
        repeat
                min:=maxc;u:=0;
                for i:=1 to n do
                        if cx[i] then
                        if d[i]res then res:=d[u];
                for v:=1 to n do
                        if cx[v] then
                                if d[v]>c[u,v] then
                                        begin
                                            d[v]:=c[u,v];
                                        end;
        until false;
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    readln(n,m);
    for i:=1 to n do
        for j:=1 to n do
                if i<>j then c[i,j]:=maxc else c[i,j]:=0;
    for i:=1 to m do
        begin
            readln(u,v,t);
            c[u,v]:=t;
            c[v,u]:=t;
        end;
    init;
    prim;
    writeln(res);
    close(input);close(output);
end.

Chủ đề: Kruskal, Prim, SPOJ Mức độ: kruskal, NKCITY - spoj, prim

VMRESTO – SPOJ

May 24, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/VMRESTO/

Thuật toán:

Thuật toán bài này khá đơn giản. Bạn có thể đọc code của mình bên dưới, mình viết code cũng khá dễ đọc.

Code:

const   fi='';
        fo='';
        maxn=100;
var     hang,cot:array[1..maxn] of int64;
        cheo,n,i,j,k:longint;
        a:array[1..maxn,1..maxn] of int64;
        res,hold:int64;
procedure nhap;
begin
    assign(input,fi);reset(input);

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

    close(input);
end;
procedure init;
begin
    for i:=1 to n do
        for j:=1 to n do
                begin
                        inc(hang[i],a[i,j]);
                        inc(cot[j],a[i,j]);
                end;
end;
procedure xuly;
begin
    hold:=0;
    for i:=2 to n do
      begin
        a[i,i]:=hang[1]-hang[i];
        inc(hold,a[i,i]);
      end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
    res:=(hang[1]-hold) div (n-1);
    for i:=1 to n  do
        begin
            for j:=1 to n do
                if i<>j then write(a[i,j],' ') else write(res+a[i,j],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.

Chủ đề: SPOJ Mức độ: VMRESTO - spoj

BGBOARD – SPOJ

May 24, 2016 by Aida Nana 2 Comments

Đề bài: http://vn.spoj.com/problems/SKPV15_5/

Thuật toán:

(đang cập nhập)

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair  pii;
typedef pair  pll;
typedef pair  pdd;
typedef vector  vi;
typedef vector  vll;
typedef vector  vd;
typedef vector  vs;
typedef map  mpsi;
typedef map  mpdi;
typedef map  mpii;

const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

template  inline T abs1(T a) {return a < 0 ? -a : a;}

template  inline T max1(T a, T b) { return a > b ? a : b; }
template  inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template  inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template  inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template  inline T min1(T a, T b) { return a < b ? a : b; }
template  inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template  inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template  inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }

inline int jud(double a, double b){
	if(abs(a) < eps && abs(b) < eps) return 0;
	else if(abs1(a - b) / abs1(a) < eps) return 0;
	if(a < b) return -1;
	return 1;
}
template  inline int jud(t a, t b){
	if(a < b) return -1;
	if(a == b) return 0;
	return 1;
}

// f_lb == 1ï¿½ï¿½?ï¿½ï¿½ï¿½ï¿½Í¬ï¿½ï¿½Ò»ï¿½ï¿½ï¿½ï¿½ï¿½ï¿½ß½ç£¬f_small == 1ï¿½ï¿½?ï¿½ï¿½ï¿½ï¿½ï¿½Ã»ï¿½ï¿½Ñ°ï¿½Òµï¿½Öµï¿½ï¿½ï¿½ï¿½Ð¡ï¿½ï¿½ï¿½ï¿½
template 
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
	int be = 0, en = na - 1;
	if(*a <= *(a + na - 1)){
		if(f_lb == 0) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != 1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != -1) en = mid;
			else be = mid + 1;
		}
		if(f_small && jud(*(a + be), val) == 1) be--;
		if(!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if(f_lb) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != -1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != 1) en = mid;
			else be = mid + 1;
		}
		if(!f_small && jud(*(a + be), val) == -1) be--;
		if(f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}



template  inline T lowb(T num) {return num & (-num); }
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }

long long pow(long long n, long long m, long long mod = 0){
	if(m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while(m){
		if(m & 1) {
			ans *= k;
			if(mod) ans %= mod;
		}
		k *= k;
		if(mod) k %= mod;
		m >>= 1;
	}
	return ans;
}

//#define debug
//.........................ï¿½ï¿½.......ï¿½ï¿½.......ï¿½ï¿½.......ï¿½ï¿½.......ï¿½ï¿½.......Ö¹.......hack...............................................

const int maxn = 5000;
int dp[maxn][maxn];
int arr[maxn][maxn];
mpii biao[maxn * maxn];
int n, m;

int main(){
    ios_base::sync_with_stdio(0);
	#ifdef debug //......................................................................................................
	freopen("input.txt", "r", stdin);
	#endif //...........................................................................................................
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
		scanf("%d", arr[i] + j);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		 for(int j = 0; j < m; j++) {
			 mpii :: iterator it;
			 it = biao[arr[i][j]].begin();
			 for(; it != biao[arr[i][j]].end(); it++) {
				 int a = it->first, b = j;
				 if(a > b) swap(a, b);
				 dp[a][b] = max(it->second, dp[a][b]);
			 }
			 biao[arr[i][j]][j] = i + 1;
		 }
		 for(int j = 1; j < m; j++) for(int k = 0; k < m - j; k++)
			 dp[k][k + j] = max1(dp[k][k + j], dp[k][k + j - 1], dp[k + 1][k + j]);
		 for(int j = 0; j < m; j++) for(int k = j; k < m; k++) {
			 ans = max1(ans, (i - dp[j][k] + 1) * (k - j + 1));
		 }
	}
	cout << ans << endl;
    return 0;
}

Chủ đề: Quy hoạch động, SPOJ

V8SCORE – SPOJ

QBMARKET – SPOJ

MMOD29 – SPOJ

QBROBOT – SPOJ

CATALAN – SPOJ

MINCUT – SPOJ

VMKEY – SPOJ

NKCITY – SPOJ

VMRESTO – SPOJ

BGBOARD – SPOJ

Recent Posts

Recent Comments

Archives

Categories

Meta