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
#include "kanapka.h"
#include "message.h"
#include <iostream>
#include <cstdio>
using namespace std;

#define LLI long long int
using namespace std;

LLI n, ssuf[200], spref[200], nodes, tab[100100], mmax[200], mmax2[200];
//*********************************************************************************
int main()
{
    //scanf("%lld%lld", &n, &nodes);
    //for(int i = 0; i < n; i++) scanf("%lld", &tab[i]);
    n = GetN();
    nodes = NumberOfNodes();
    //n++;

    if(MyNodeId() > 0)
    {
        int i = MyNodeId();
        int p = ((i - 1) * n) / (nodes - 1);
        int k = (i * n) / (nodes - 1);
        //cout << p << " " << k << endl;
        LLI sum = 0;
        for(int j = p; j < k; j++)
            sum += GetTaste(j);
            //cout << j << ": " << sum << endl;
        PutLL(0, sum);
        Send(0);
        //spref[i] = sum;
        //ssuf[i] = sum;
    }
    else
    {
        for(int i = 1; i < nodes; i++)
        {
            Receive(i);
            spref[i] = GetLL(i);
            ssuf[i] = spref[i];
        }
        for(int i = 1; i < nodes; i++)
            spref[i] += spref[i - 1];
        for(int i = nodes - 1; i >= 1; i--)
            ssuf[i] += ssuf[i + 1];
        for(int i = 1; i < nodes; i++)
            PutLL(i, spref[i - 1]),
            PutLL(i, ssuf[i]),
            Send(i);
    }
    //for(int i = 1; i < nodes; i++) cout << i << ": " << spref[i] << " " << ssuf[i] << endl;

    //cout << ssuf[1] << " " << spref[1] << endl;
    //for(int i = 1; i < nodes; i++) cout << i << ": " << spref[i] << " " << ssuf[i] << endl;
    LLI wynik = -1e17;
    if(MyNodeId() > 0)
    {
        int i = MyNodeId();
        int p = ((i - 1) * n) / (nodes - 1);
        int k = (i * n) / (nodes - 1);
        Receive(0);
        LLI pref = GetLL(0), maxx = pref, sum = GetLL(0), msum = sum;
        for(int j = p; j < k; j++)
        {
            pref += GetTaste(j);
            if(pref > maxx) maxx = pref;
            mmax[i] = maxx;
            sum -= GetTaste(j);
            if(sum > msum) msum = sum;
            mmax2[i] = msum;
            //cout << j << ": " << pref << " " << sum << endl;
            wynik = max(wynik, sum + maxx);
        }
        PutLL(0, mmax[i]);
        PutLL(0, mmax2[i]);
        PutLL(0, wynik);
        Send(0);
    }
    else
    {
        for(int i = 1; i < nodes; i++)
        {
            Receive(i);
            mmax[i] = GetLL(i);
            mmax2[i] = GetLL(i);
            wynik = max(wynik, GetLL(i));
        }
        mmax[0] = -1e17;
        mmax2[nodes] = -1e17;
        for(int i = 1; i < nodes; i++)
            mmax[i] = max(mmax[i - 1], mmax[i]);
        for(int i = nodes - 1; i >= 1; i--)
            mmax2[i] = max(mmax2[i+1], mmax2[i]);
        for(int i = 1; i < nodes; i++)
            //cout << i << ": " << mmax[i] << " " << mmax2[i + 1] << endl,
            wynik = max(wynik, mmax[i] + mmax2[i + 1]);
        printf("%lld\n", max(0ll, wynik));
    }
}