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
119
120
121
#include "message.h"

#include <iostream>
#include "maklib.h" 

using namespace std;

#define DBG(X)

long long tabSum[200];
long long tabmaxSumFront[200];
long long tabmaxSumEnd[200];
long long tabmaxSumGlobal[200];


int main() {
  
  int n = Size();
  
  if (n < 10000)
  {
    if (MyNodeId() == 0)
    {
    
      long long maxSumEnd = 0;
      long long maxSumGlobal = 0;
      
      for (int i = 1; i <= n; i++)
      {
        int elem = ElementAt(i);
        maxSumEnd = max(maxSumEnd + elem, 0LL);
        maxSumGlobal = max(maxSumGlobal, maxSumEnd);
      }
    
      cout << maxSumGlobal << endl;
    }
    return 0;
  }
  
  int m = (n + NumberOfNodes() - 1) / NumberOfNodes();

  long long sum = 0;
  long long maxSumFront = 0;
  long long maxSumEnd = 0;
  long long maxSumGlobal = 0;
    
  for (int i = MyNodeId() * m + 1; i <= min((MyNodeId() + 1) * m, n); i++)
  {
    int elem = ElementAt(i);
    sum += elem;
    maxSumEnd = max(maxSumEnd + elem, 0LL);
    maxSumGlobal = max(maxSumGlobal, maxSumEnd);

    maxSumFront = max(maxSumFront, sum);
  }

  
  if (MyNodeId() > 0) 
  {
    PutLL(0, sum);
    PutLL(0, maxSumFront);
    PutLL(0, maxSumEnd);
    PutLL(0, maxSumGlobal);
    Send(0);
  } else 
  {
    tabSum[0] = sum;
    tabmaxSumFront[0] = maxSumFront;
    tabmaxSumEnd[0] = maxSumEnd;
    tabmaxSumGlobal[0] = maxSumGlobal;
  //  cout << tabSum[0] << endl;
    for (int instancja = 1; instancja < NumberOfNodes(); ++instancja) 
    {
      Receive(instancja);
      tabSum[instancja] = GetLL(instancja);
      tabmaxSumFront[instancja] = GetLL(instancja);
      tabmaxSumEnd[instancja] = GetLL(instancja);
      tabmaxSumGlobal[instancja] = GetLL(instancja);
      
    //  cout << tabSum[instancja] << endl;
      
    }
    
    //przypadek 1 - global max
    long long globRet = 0;
    for (int i = 0; i < NumberOfNodes(); i++)
    {
      globRet = max(globRet, tabmaxSumGlobal[i]);
    }
    
    DBG(cout << "1 globRet " << globRet << endl;)
    
    //przypadek 2 - zachodzace front-endy
    
    for (int i = 0; i < NumberOfNodes() - 1; i++)
    {
      globRet = max(globRet, tabmaxSumEnd[i] + tabmaxSumFront[i + 1]);
    }
    
    DBG(cout << "2 globRet " << globRet << endl;)
    
    //przypadek 3 - front - sumy - end
    for (int i = 0; i < NumberOfNodes() - 2; i++)
    {
      long long pref = tabmaxSumEnd[i];
      long long s = 0;
      for (int j = i + 1; j < NumberOfNodes() - 1; j++)
      {
        s += tabSum[j];
        globRet = max(globRet, pref + s + tabmaxSumFront[j + 1]);
      }
    }
    
    DBG(cout << "3 globRet " << globRet << endl;)
    
    cout << globRet << endl;
    
  }
  
  return 0;
}