weight2.pas 1.6 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788
  1. program hxy;
  2. Const maxn=1000;
  3. maxw=1000000;
  4. infile='weight.in';
  5. outfile='weight.out';
  6. Var a:array[1..2*maxn]of longint;
  7. used:array[1..2*maxn]of boolean;
  8. bool:array[0..maxn]of boolean;
  9. Ans:array[0..maxn]of longint;
  10. n,m,Tot,wHead,wNil:longint;
  11. procedure Qsort(x,y:longint);
  12. var xx,yy,k:longint;
  13. begin
  14. if x>=y then exit;
  15. xx:=x; yy:=y; k:=a[x];
  16. repeat
  17. while (xx<yy) and (k<=a[yy]) do dec(yy);
  18. if xx<yy then a[xx]:=a[yy];
  19. while (xx<yy) and (k>=a[xx]) do inc(xx);
  20. if xx<yy then a[yy]:=a[xx];
  21. until xx=yy;
  22. a[xx]:=k;
  23. Qsort(x,xx-1);
  24. Qsort(xx+1,y);
  25. end;
  26. procedure DataIn;
  27. var i,j:longint;
  28. begin
  29. fillchar(bool,sizeof(bool),0);
  30. fillchar(used,sizeof(used),0);
  31. Tot:=0;
  32. readln(n,m);
  33. for i:=1 to m do
  34. begin
  35. read(j);
  36. bool[j]:=true;
  37. end;
  38. readln;
  39. for i:=1 to 2*n do
  40. begin
  41. read(a[i]);
  42. if a[i]>Tot then Tot:=a[i];
  43. end;
  44. readln;
  45. Qsort(1,2*n);
  46. wHead:=0; wNil:=0;
  47. end;
  48. procedure OutAns;
  49. var i,j:longint;
  50. begin
  51. assign(output,outfile);
  52. rewrite(output);
  53. for i:=1 to n-1 do write(Ans[i],' ');
  54. writeln(Ans[n]);
  55. close(output);
  56. end;
  57. procedure Try(x,y:longint);
  58. var i,j,k,step:longint;
  59. begin
  60. if x+2=y then
  61. begin
  62. Ans[x+1]:=Tot-wHead-wNil;
  63. OutAns;
  64. halt
  65. end;
  66. step:=x+(n-y+1)+1;
  67. if (bool[a[step]-wHead]) then
  68. begin
  69. Ans[x+1]:=a[step]-wHead;
  70. wHead:=a[step];
  71. Try(x+1,y);
  72. dec(wHead,Ans[x+1]);
  73. end;
  74. if bool[a[step]-wNil] then
  75. begin
  76. Ans[y-1]:=a[step]-wNil;
  77. wNil:=a[step];
  78. Try(x,y-1);
  79. dec(wNil,Ans[y-1]);
  80. end;
  81. end;
  82. begin
  83. assign(input,infile);
  84. reset(input);
  85. DataIn;
  86. Try(0,n+1);
  87. close(input);
  88. end.