1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
uses 
  maklib, message;

const
  ndx=100;
  
type 
 i4=longint;
 i8=int64;

var 
  nr,nd, nel : i4;
  sl,sr,sm,s : i8;

function Max(a, b : i8): i8; inline; 
begin if a > b then Max := a else Max := b; end;

procedure seg(a,b:i4);
var x:i8; i:i4;
begin
  s:=ElementAt(a);
  sm:=s;
  sl:=s;
  sr:=s;
  for i:=a+1 to b do begin
    x:=ElementAt(i);
    s+=x;
    sl:=max(sl,s);
    sr:=max(sr+x,x);
    sm:=max(sm,sr);
  end;
end;

procedure run1;
var n,a,b:i4;
begin
  n:=Receive(0);
  a := GetInt(n);
  b := GetInt(n);
  if a<0 then  exit;

  seg(a,b);

  PutLL( n, sl );
  PutLL( n, sr );
  PutLL( n, sm );
  PutLL( n, s  );
  Send( n );
end;

procedure get(n:i4);
var n1:i4;
begin
  n1:=Receive(n);
  sl := GetLL( n );
  sr := GetLL( n );
  sm := GetLL( n );
  s  := GetLL( n );
end;

procedure put(n,a,b:i4);
begin
  PutInt( n, a );
  PutInt( n, b );
  Send( n );
end;

function min(a, b : i4): i4; inline;
begin
  if a < b then min := a else min := b;
end;

procedure obl(a,b,q:i4);
var
  i:i4;
  x,y:i8;
begin
  seg(a,b);
  x:=sr;
  y:=sm;
  
  for i:=1 to q do begin
    get(i);
    y:=max(y,x+sl);
    x:=max(x+s,sr);
    y:=max(y,max(x,sm));
  end;

  writeln(y);
end;

procedure run(k:i4);
var q,i,j:i4;
begin
  i:=1+k;
  q:=0;
  while i<=nel do begin
    q+=1;
    j:=min(nel,i-1+k);
    put(q,i,j);
    i:=j+1;
  end;
  
  for i:=q+1 to nd-1 do put(i,-1,-1);
  obl(1,k,q);
end;

var k:i4;
begin
  nel:=size();
  nr:=MyNodeId;
  nd:=NumberOfNodes;
  if nr>0 then begin run1; exit; end;

  k:=(nel-1+nd) div nd;
  k:=max(k,min(nel,1000000));
  run(k);
end.