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
#include "maklib.h"
#include "message.h"
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL podciag(int poc, int kon)
{
  LL ret = 0;
  LL S = 0;
  for(int i=poc+1; i<=kon; i++)
  {
    S += ElementAt(i);
    S = max(S, 0LL);
    ret = max(ret, S);
  }
  return ret;
}
int main()
{
  int n = Size();
  int poczatek = MyNodeId() * n / NumberOfNodes();
  int koniec = (MyNodeId() + 1) * n / NumberOfNodes();
  LL wynik = 0;
  LL suma = 0;
  LL bestpref = 0;
  for(int i=poczatek+1; i<=koniec; i++)
  {
    LL x = ElementAt(i);
    suma += x;
    bestpref = max(suma, bestpref);
  }
  suma = 0;
  LL bestsuf = 0;
  for(int i=koniec; i>poczatek; i--)
  {
    suma += ElementAt(i);
    bestsuf = max(suma, bestsuf);
  }
  wynik = podciag(poczatek, koniec);
  if(MyNodeId() > 0)
  {
    PutLL(0, suma);
    PutLL(0, bestpref);
    PutLL(0, bestsuf);
    PutLL(0, wynik);
    Send(0);
  }
  else
  {    
    for(int i=1; i<NumberOfNodes(); i++)
    {
      Receive(i);
      LL sumanext = GetLL(i);
      LL bestprefnext = GetLL(i);
      LL bestsufnext = GetLL(i);
      LL wyniknext = GetLL(i);
      wynik = max(wynik, max(wyniknext, bestsuf + bestprefnext));
      bestsufnext = max(bestsufnext, sumanext + bestsuf);
      bestsuf = bestsufnext;
    }
    printf("%lld", wynik);
  } 
  return 0;
}