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

#include <vector>
#include <cstdio>
#define LL long long int
using namespace std;

struct S
{
    S(LL kad, LL left, LL right, LL sum) : kad(kad), left(left), right(right), sum(sum) {}
    LL kad, left, right, sum;
};


int main()
{
    int M = NumberOfNodes();
    int ID = MyNodeId();
    int n = Size();
//--------------------------------------------------------------------------------------
    if(M*4 > n || M == 1)
    {
        if(ID == 0)
        {
            LL maxk = 0, curr = 0;
            for(int i = 0; i < n; ++i)
            {
                int t = ElementAt(i+1);
                if(curr < 0)
                    curr = t;
                else
                    curr += t;
                maxk = max(maxk, curr);
            }
            printf("%lld\n", maxk);
        }
        return 0;
    }
//--------------------------------------------------------------------------------------
    if(ID == 0)
    {
        vector<S> v1, v2;
        for(int i = 1; i < M; ++i)
        {
            Receive(i);
            LL kad = GetLL(i);
            LL left = GetLL(i);
            LL right = GetLL(i);
            LL sum = GetLL(i);
            v1.push_back(S(kad, left, right, sum));
        }

        vector<S> *curr = &v1, *concurr = &v2;
        while(curr->size() > 1)
        {
            concurr->clear();
            int kon = (curr->size()/2)*2;
            for(int i = 0; i < kon; i+=2)
            {
                LL nmax = max(max((*curr)[i].kad, (*curr)[i+1].kad), (*curr)[i].right + (*curr)[i+1].left);
                LL nleft = max((*curr)[i].left, (*curr)[i].sum+(*curr)[i+1].left);
                LL nright = max((*curr)[i+1].right, (*curr)[i+1].sum+(*curr)[i].right);
                LL nsum = (*curr)[i].sum + (*curr)[i+1].sum;
                concurr->push_back(S(nmax, nleft, nright, nsum));
            }
            if(curr->size()%2 == 1)
                concurr->push_back((*curr)[curr->size()-1]);
            swap(curr, concurr);
        }
        printf("%lld\n", (*curr)[0].kad);
    }
//--------------------------------------------------------------------------------------
    else
    {
        int p = ((ID-1)*n)/(M-1), k = ((ID)*n)/(M-1);
        LL kadan = 0, curr = 0, left = 0, right = 0, sum = 0, rsum = 0;
        for(int i = p; i < k; ++i)
        {
            int t = ElementAt(i+1);
            if(curr < 0)
                curr = t;
            else
                curr += t;
            kadan = max(kadan, curr);
            sum += t;
            left = max(left, sum);
        }
        for(int i = k-1; i >= p; --i)
        {
            rsum += ElementAt(i+1);
            right = max(right, rsum);
        }
        PutLL(0, kadan);
        PutLL(0, left);
        PutLL(0, right);
        PutLL(0, sum);
        Send(0);
    }
    return 0;
}