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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <math.h>
#include "maklib.h"
#include "message.h"

using namespace std;
 

int main()
{
  
  int blockSize = ( Size() + NumberOfNodes() - 1 ) / NumberOfNodes();
  int BEGIN = MyNodeId() * blockSize;
  int END = min(Size(), (MyNodeId() + 1) * blockSize);

//   cout << MyNodeId() << ": BEG, END =  " << BEGIN << " " << END << "\n";
  long long bestSoFar= 0;
  long long bestEndingHere = 0;
  long long sum = 0;
   
  for(int i = BEGIN; i < END; i++)
  {
    int curr = ElementAt(i+1);
    bestEndingHere = max(0LL, bestEndingHere + curr);
    bestSoFar = max(bestSoFar, bestEndingHere);
    sum += curr;
  }
    
  long long best = bestSoFar;
  long long bestToRight = bestEndingHere;
  bestEndingHere = 0;
  
  for(int i = END - 1; i >= BEGIN; i--)
  {
    int curr = ElementAt(i+1);
    bestEndingHere = max(0LL, bestEndingHere + curr);
  }  
  
  long long bestToLeft= bestEndingHere;
  
  PutLL(0,bestToLeft);
  PutLL(0,best);
  PutLL(0,bestToRight);
  PutLL(0,sum);
  Send(0);
  
//   cout << MyNodeId() << ": " << bestToLeft << " " << best << " " << bestToRight << " " << sum << "\n";
 
  if( MyNodeId() > 0)
    return 0;
  
  long long globalBest = best;
  long long currentBest = bestToRight;
  for(int i = 1; i < NumberOfNodes(); i++)
  {
    Receive(i);
    long long toLeft = GetLL(i);
    best = GetLL(i);
    long long toRight = GetLL(i);
    long long toSum = GetLL(i); 
    globalBest = max(globalBest, currentBest + toLeft);
    currentBest = max(currentBest + toSum, toRight);
    globalBest = max(globalBest, best);
    globalBest = max(globalBest, currentBest);
  }
  
  cout << globalBest;
  
  return 0;
}