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
#include "kanapka.h"
#include "message.h"
#include <cstdio>

const int MAX_NODES = 1000;

struct partial_sum {
  long long whole;
  long long max;
  long long maxn;
  
  partial_sum() :
   whole(0), max(0), maxn(-1) {
  }
  
  partial_sum& operator+=(long long num) {
    whole += GetTaste(num);
    if (whole > max) {
      max = whole;
      maxn = num;
    }
    return *this;
  }
  
  static partial_sum lsum(long long a, long long b) {
    //fprintf(stderr, "lsum %lld %lld: ", a, b);
    partial_sum s;
    for (; a < b; ++a) {
      s += a;
    }
    //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn);
    return s;
  }
  
  static partial_sum rsum(long long a, long long b) {
    //fprintf(stderr, "rsum %lld %lld: ", a, b);
    partial_sum s;
    for (; a > b; --a) {
      s += a;
    }
    //fprintf(stderr, " %lld %lld %lld\n", s.whole, s.max, s.maxn);
    return s;
  }
  
  partial_sum& operator+=(const partial_sum& other) {
    if (whole+other.max > max) {
      max = whole+other.max;
      maxn = other.maxn;
    }
    whole += other.whole;
  }
  
  void write(int dst) const {
    PutLL(dst, whole);
    PutLL(dst, max);
    PutLL(dst, maxn);
    Send(dst);
  }
  
  static partial_sum read(int src) {
    partial_sum s;
    Receive(src);
    s.whole = GetLL(src);
    s.max = GetLL(src);
    s.maxn = GetLL(src);
    return s;
  }
};

int main() {
  partial_sum lsum, rsum;
  const long long partition = GetN()/NumberOfNodes();
  if (MyNodeId() == NumberOfNodes()-1)
    lsum = partial_sum::lsum(partition*MyNodeId(), GetN());
  else
    lsum = partial_sum::lsum(partition*MyNodeId(), partition*(MyNodeId()+1));
  if (MyNodeId() == 0) {
    for (int i = 1; i < NumberOfNodes(); ++i) {
      lsum += partial_sum::read(i);
    }
    for (int i = 1; i < NumberOfNodes(); ++i) {
      PutLL(i, lsum.maxn);
      Send(i);
    }
    const long long rpart = (GetN()-lsum.maxn-1)/NumberOfNodes();
    rsum = partial_sum::rsum(GetN()-1, GetN()-rpart*(MyNodeId()+1)-1);
    for (int i = 1; i < NumberOfNodes(); ++i) {
      rsum += partial_sum::read(i);
    }
    printf("%lld\n", lsum.max+rsum.max);
  } else {
    lsum.write(0);
    Receive(0);
    const long long maxl = GetLL(0);
    const long long rpart = (GetN()-maxl-1)/NumberOfNodes();
    if (MyNodeId() == NumberOfNodes()-1)
      rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, maxl);
    else
      rsum = partial_sum::rsum(GetN()-rpart*MyNodeId()-1, GetN()-rpart*(MyNodeId()+1)-1);
    rsum.write(0);
  }
}