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

using namespace std;

#ifdef WTF
#include "maklib.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static int n;
static int* data;

static void Init() {
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  assert(1 == scanf("%d", &n));
  data = (int*)malloc((n + 1) * sizeof(int));
  assert(data != NULL);
  for (i = 1; i <= n; ++i) {
    assert(1 == scanf("%d", data + i));
  }
  initialized = 1;
}

int Size() {
  Init();
  return n;
}

int ElementAt(int i) {
  Init();
  assert(1 <= i && i <= n);
  return data[i];
}
#endif // WTF

long long pref=0,sum=0,maxsum=0,suf=0,minsuf=0;

int main(){
    if(NumberOfNodes()<Size()){
        long long tbeg=MyNodeId()*(Size()/NumberOfNodes())+1,tend=(MyNodeId()==(NumberOfNodes()-1)) ? Size() : (MyNodeId()+1)*(Size()/NumberOfNodes());
        for(int i=tend;i>=tbeg;--i){
            sum+=ElementAt(i);
            suf=max(suf,sum);
            minsuf=min(minsuf,sum);
            maxsum=max(maxsum,sum-minsuf);
        }
        sum=0;
        for(int i=tbeg;i<=tend;++i){
            sum+=ElementAt(i);
            pref=max(pref,sum);
        }
        if(MyNodeId()){
            PutLL(0,pref);
            PutLL(0,sum);
            PutLL(0,maxsum);
            PutLL(0,suf);
            Send(0);
        }else{
            for(int i=1;i<NumberOfNodes();++i){
                long long rpref,rsum,rmaxsum,rsuf;
                Receive(i);
                rpref=GetLL(i);
                rsum=GetLL(i);
                rmaxsum=GetLL(i);
                rsuf=GetLL(i);

                maxsum=max(maxsum,max(suf+rpref,rmaxsum));
                pref=max(pref,sum+rpref);
                suf=max(rsuf,suf+rsum);
                sum+=rsum;
            }
            printf("%lld",maxsum);
        }
    }else if(!MyNodeId()){
        for(int i=Size();i>=1;--i){
            sum+=ElementAt(i);
            suf=max(suf,sum);
            minsuf=min(minsuf,sum);
            maxsum=max(maxsum,sum-minsuf);
        }
        printf("%lld",maxsum);
    }
    return 0;
}