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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <cstdio>
#include <algorithm>
#include <vector>

#include "kanapka.h"
#include "message.h"

struct Data { long long Sum, MaxL, MaxR, Best; };

static void printData(const Data &data)
{
//  printf("{ .Sum=%lld .MaxL=%lld .MaxR=%lld .Best=%lld }\n",
//         data.Sum, data.MaxL, data.MaxR, data.Best);
}

static void getMyValues(std::vector<int> &V)
{
  assert(V.empty());

  int n = GetN();
  int nodes = (int)NumberOfNodes();
  int X = n / nodes;
  V.reserve(X + 4);
  int E;

  if (MyNodeId() == nodes - 1)
    E = n;
  else
    E = (MyNodeId() * X) + X;

  for (int i = MyNodeId() * X; i < E; ++i)
  {
    int v = GetTaste(i);
//    printf("[%d] gets %d\n", MyNodeId(), v);
    V.push_back(v);
  }
}

static const Data getMyData(const std::vector<int> &V)
{
  std::vector<long long> MaxR(V.size());

  long long currR = 0;
  long long tmpR = 0;

  for (int i = V.size() - 1; i >= 0; --i)
  {
    currR += V[i];
    MaxR[i] = tmpR = std::max(currR, tmpR);
  }


  long long currL = 0;
  long long tmpL = 0;

  long long best = 0;

  for (int i = 0; i < V.size(); ++i)
  {
    currL += V[i];

    // imporant, do it before tmpL is computed
    best = std::max(best, tmpL + MaxR[i]);

    tmpL = std::max(currL, tmpL);
  }

  assert(currL == currR);

  Data data;
  data.Sum = currL;
  data.MaxL = tmpL;
  data.MaxR = tmpR;
  data.Best = best;

  return data;
}


int main()
{
  std::vector<int> V;

  getMyValues(V);

  const Data myData = getMyData(V);

  if (MyNodeId())
  {
    PutLL(0, myData.Sum);
    PutLL(0, myData.MaxL);
    PutLL(0, myData.MaxR);
    PutLL(0, myData.Best);
    Send(0);
    return 0;
  }

  const int nodes = (int)NumberOfNodes();
  Data *data = new Data[nodes];
  data[0] = myData;

//  printf("data[0] = ");
  printData(data[0]);

  for (int i = 1; i < nodes; ++i)
  {
    Receive(i);
    data[i].Sum = GetLL(i);
    data[i].MaxL = GetLL(i);
    data[i].MaxR = GetLL(i);
    data[i].Best = GetLL(i);

//    printf("data[%d] = ", i);
    printData(data[i]);
  }

  long long *maxR = new long long[nodes];
  long long *valR = new long long[nodes];
  long long currR = 0;
  long long tmpR = 0;
  for (int i = nodes - 1; i >= 0; --i)
  {
    long long oldR = currR;

    currR += data[i].Sum;
    valR[i] = currR;
    maxR[i] = tmpR = std::max(tmpR, oldR + data[i].MaxR);

//    printf("maxR[%d] = %lld\n", i, maxR[i]);
  }

  long long valL = 0;
  long long maxL = 0;

  long long best = 0;

  for (int i = 0; i < nodes; ++i)
  {
    long long v1 = valL + data[i].Best + (i < nodes - 1 ? valR[i+1] : 0);
    long long v2 = valL + data[i].MaxL + (i < nodes - 1 ? maxR[i+1] : 0);
    long long v3 = maxL + data[i].MaxR + (i < nodes - 1 ? valR[i+1] : 0);
    long long v4 = maxL + 0            + (i < nodes - 1 ? maxR[i+1] : 0);

//    printf("%d: maxL=%lld valL=%lld   v1=%lld v2=%lld v3=%lld v4=%lld\n",
//           i, maxL, valL, v1, v2, v3, v4);

    best = std::max(best, v1);
    best = std::max(best, v2);
    best = std::max(best, v3);
    best = std::max(best, v4);

    valL += data[i].Sum;
    maxL = std::max(valL, maxL);
  }


  printf("%lld\n", best);
}