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
#define PB push_back
#define MP make_pair
#define LL long long int

#include "kanapka.h"
#include "message.h"
#include <cstdio>
#include <vector>

using namespace std;

LL getBeg(LL n, LL k, LL piece, LL id) {
  if (n >= k) {
    return id * piece;
  } else {
    return id < n ? id : -1;
  }
}

LL getEnd(LL n, LL k, LL piece, LL id) {
  if (n >= k) {
    return id == k - 1 ? n - 1 : ((id + 1) * piece) - 1;
  } else {
    return id < n ? id : -1;
  }
}

int main() {
  LL n = GetN();
  LL k = NumberOfNodes();
  LL id = MyNodeId();
  LL piece = n / k;
  LL beg = getBeg(n, k, piece, id);
  LL end = getEnd(n, k, piece, id);

  LL leftPos = -1;
  LL leftResult = 0;
  LL leftSum = 0;

  

  if (id < n)  {
    for (LL i = beg; i <= end; ++i) {
      leftSum += GetTaste(i);
      if (leftSum > leftResult) {
        leftResult = leftSum;
        leftPos = i;
      }
    }
  }

  LL rightPos = -1;
  LL rightResult = 0;
  LL rightSum = 0;

  if (id < n) {
    for (LL i = end; i >= beg; --i) {
      rightSum += GetTaste(i);
      if (rightSum > rightResult) {
        rightResult = rightSum;
        rightPos = i;
      }
    }
  }

  if (id != 0 && id < n) {
    PutLL(0, leftPos);
    PutLL(0, leftResult);
    PutLL(0, leftSum);
    Send(0);
    PutLL(0, rightPos);
    PutLL(0, rightResult);
    PutLL(0, rightSum);
    Send(0);
  } else if (id == 0) {
    if (k > n) {
      k = n;
    }
    vector<pair<LL, LL> > left, right;
    LL leftS = 0, rightS = 0;

    left.PB(MP(leftPos, leftResult));
    leftS += leftSum;

    for (LL i = 1; i < k; ++i) {
      Receive(i);
      LL pos = GetLL(i);
      LL res = GetLL(i);
      LL sum = GetLL(i);

      if (left[left.size() - 1].second < leftS + res) {
        left.PB(MP(pos, leftS + res));
      } else {
        left.PB(left[left.size() - 1]);
      }

      leftS += sum;
    }

    right.PB(MP(-1, 0));

    for (LL i = k - 1; i > 0; --i) {
      Receive(i);
      LL pos = GetLL(i);
      LL res = GetLL(i);
      LL sum = GetLL(i);

      if (right[right.size() - 1].second < rightS + res) {
        right.PB(MP(pos, rightS + res));
      } else {
        right.PB(right[right.size() - 1]);
      }

      rightS += sum;
    }

    if (right[right.size() - 1].second < rightS + rightResult) {
      right.PB(MP(rightPos, rightS + rightResult));
    } else {
      right.PB(right[right.size() - 1]);
    }

    LL result = leftS;

    for (LL i = 0; i < left.size(); ++i) {
      LL x = left.size() - i;
      if (right[x].first <= left[i].first) {
        --x;
      }
      result = max(result, left[i].second + right[x].second);
    }

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