fork download
copy 
  1. Program DTtui1;
  2. CONST
  3.         fin='';
  4.         fon='';
  5.         maxn=40;
  6.         maxth=1048576;
  7. Type
  8.         Opt=Record
  9.                 kl,gt:longint;          //Khoi luong, Gia tri
  10.         End;
  11.         ToHop=array [1..maxth] of Opt;
  12. Var
  13.         o:array [1..2] of ToHop;
  14.         dem:array [1..2] of longint;
  15.         amax:array [1..maxth] of longint;
  16.         w,v:array [1..maxn] of longint;   //Weight, Value
  17.         m,i,j,sw,sv,sum:longint;
  18.         n,mid:byte;
  19.         f:text;
  20. //--------------------------------------------------
  21.         Procedure Nhap;
  22.         Var i:byte;
  23.         Begin
  24.                 Assign(f,fin);
  25.                 Reset(f);
  26.                 Readln(f,n,m);
  27.                 For i:=1 to n do
  28.                         Readln(f,w[i],v[i]);
  29.                 Close(f);
  30.         ENd;
  31.         //------------------------------------------
  32.  
  33.                 Procedure Sort(l,r:longint);
  34.                 Var i,j,x:longint;
  35.                         y:Opt;
  36.                 Begin
  37.                         i:=l;
  38.                         j:=r;
  39.                         x:=o[2,l+random(r-l+1)].kl;
  40.                         Repeat
  41.                                 While o[2,i].kl<x Do inc(i);
  42.                                 While o[2,j].kl>x do dec(j);
  43.                                 If not(i>j) Then
  44.                                         Begin
  45.                                         y:=o[2,i];
  46.                                         o[2,i]:=o[2,j];
  47.                                         o[2,j]:=y;
  48.                                         inc(i);
  49.                                         dec(j);
  50.                                         ENd;
  51.                         Until i>j;
  52.                         If i<r Then sort(i,r);
  53.                         If l<j Then sort(l,j);
  54.                 End;
  55.         //-----------------------------------------
  56.         Procedure Luu(x:byte);
  57.         Var k:longint;
  58.         Begin
  59.                 inc(dem[x]);
  60.                 k:=dem[x];
  61.                 o[x,k].kl:=sw;
  62.                 o[x,k].gt:=sv;
  63.         End;
  64.         //----------------------------------------
  65.         Procedure Duyet(bit,i,k:byte);
  66.         Var j:byte;
  67.         Begin
  68.                 If sw>m Then Exit;
  69.                 For j:=0 to 1 do
  70.                         Begin
  71.                         sw:=sw+j*w[i];
  72.                         sv:=sv+j*v[i];
  73.                         If i=k Then
  74.                                 Begin
  75.                                 If sw<=m Then Luu(bit);
  76.                                 End
  77.                         else Duyet(bit,i+1,k);
  78.                         sw:=sw-j*w[i];
  79.                         sv:=sv-j*v[i];
  80.                         End;
  81.         End;
  82.         //-------------------------------------
  83.         Procedure CheckMax;
  84.         Var i,max:longint;
  85.         Begin
  86.                 amax[1]:=1;
  87.                 max:=1;
  88.                 For i:=2 to dem[2] do
  89.                         Begin
  90.                         If o[2,i].gt>o[2,max].gt Then max:=i;
  91.                         amax[i]:=max;
  92.                         End;
  93.         End;
  94.         //-----------------------------------
  95.         Function Find(bit:byte; x:longint):longint;
  96.         Var dau,giua,cuoi:longint;
  97.         Begin
  98.                 dau:=1;
  99.                 cuoi:=dem[bit]+1;
  100.                 Repeat
  101.                         giua:=(dau+cuoi) div 2;
  102.                         If o[bit,giua].kl <= x Then dau:=giua
  103.                         else cuoi:=giua;
  104.                 Until dau+1=cuoi;
  105.                 Exit(dau);
  106.         End;
  107.         //------------------------------------
  108.         Procedure Xuat;
  109.         Begin
  110.                 Assign(f,fon);
  111.                 Rewrite(f);
  112.                 Writeln(f,sum);
  113.                 Close(f);
  114.         End;
  115. Begin
  116.         Randomize;
  117.         Nhap;
  118.         mid:=n div 2;
  119.         Duyet(1,1,mid);
  120.         Duyet(2,mid+1,n);
  121.         sort(1,dem[2]);
  122.         CheckMax;
  123.  
  124.         For i:=1 to dem[1] do
  125.                 Begin
  126.                 j:=Find(2,m-o[1,i].kl);
  127.                 If o[1,i].gt + o[2,amax[j]].gt > sum Then sum:=o[1,i].gt + o[2,amax[j]].gt;
  128.                 End;
  129.         Xuat;
  130. End.
Time limit exceeded #stdin #stdout 5s 20824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/eriOrN
language:
Pascal (fpc 3.0.4)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!