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
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

#include "maklib.h"
#include "message.h"

using namespace std;

typedef vector<int> VI;
typedef long long LL;

#define FOR(x, b, e) for(int x = b; x <= (e); ++x)
#define FORD(x, b, e) for(int x = b; x >= (e); --x)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define ST first
#define ND second
#define MP make_pair

#define M 1000000000000000000

LL s0=0, s1=0, s2=0;

void licz(int b, int e) {
  int x;
  LL max=0, min=0;

  FOR(i,b,e) {
    x=ElementAt(i);
    s2+=x;

    if (x>0 && s2-s0>max) {
      s0=min;
      s1=s2;
      max=s1-s0;
    }
    else if (s2<min) min=s2;
  }
}


int main() {

  if (MyNodeId()>0) {
    int b, e;

    Receive(0);
    b=GetInt(0);
    e=GetInt(0);
//cout<<"node "<<MyNodeId()<<"b e "<<b<<" "<<e<<endl;

    if (b>e) {s0=s1=s2=0;}
    else licz(b,e);

    PutLL(0,s0);
    PutLL(0,s1-s0);
    PutLL(0,s2-s1);
    Send(0);
//cout<<"node "<<MyNodeId()<<"s0,s1,s2 "<<s0<<" "<<s1<<" "<<s2<<endl;
    return 0;
  }

  int n=Size(), m=NumberOfNodes(), m1, r, d, b=1;

  m1=m-1; d=n/m1+1; r=n%m1;

  FOR(i,1,r) {
    PutInt(i, b);
    b+=d;
    PutInt(i, b-1);
    Send(i);
  }

  d--;

  FOR(i,r+1,m1) {
    PutInt(i, b);
    b+=d;
    PutInt(i, b-1);
    Send(i);
  }

  LL max=0, min=0;

  FOR(i,1,m1) {
    Receive(i);

    REP(j,3){
      LL x=GetLL(i);
      s2+=x;

      if (x>0 && s2-s0>max) {
        s0=min;
        s1=s2;
        max=s1-s0;
      }
      else if (s2<min) min=s2;
    }
  }

  cout<<s1-s0<<endl;

//  cout<<s0<<" "<<s1-s0<<" "<<s2-s1<<endl;

  return 0;
}