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

typedef long long ll;
using namespace std;

int main()
{
    int myNodeId = MyNodeId();
    int noOfNodes = NumberOfNodes();

    ll n = GetN();

    ll leftSideMax = 0;
    ll leftSideSum = 0;
    ll rightSideMax = 0;
    ll rightSideSum = 0;
    ll total = 0;
    ll bestSum = 0;
    ll bestMax = 0;

    ll start = n * myNodeId / noOfNodes;
    ll end = n * (myNodeId + 1) / noOfNodes;

    for (ll i = start; i < end; i++)
    {
        ll taste = GetTaste(i);
        leftSideSum += taste;
        bestSum += taste;
        total += taste;
        if (bestSum > 0)
        {
            bestSum = 0;
        }

        leftSideMax = leftSideMax > leftSideSum ? leftSideSum : leftSideMax;
        bestMax = bestMax > bestSum ? bestSum : bestMax;
    }
    for (ll i = end - 1; i >= start; i--)
    {
        ll taste = GetTaste(i);
        rightSideSum += taste;
        rightSideMax = rightSideMax > rightSideSum ? rightSideSum : rightSideMax;
    }

    if (myNodeId == 0)
    {
        ll lefts[101];
        ll rights[101];
        ll bests[101];
        ll totals[101];

        lefts[0] = leftSideMax;
        rights[0] = rightSideMax;
        bests[0] = bestMax;
        totals[0] = total;

        for (int i = 1; i < noOfNodes; i++)
        {
            int source = Receive(-1);
            lefts[source] = GetLL(source);
            rights[source] = GetLL(source);
            bests[source] = GetLL(source);
            totals[source] = GetLL(source);
        }

        total = 0;
        bestSum = 0;
        bestMax = 0;
        ll bestTemp = 0;

        for (int i = 0; i < noOfNodes; i++)
        {
            total += totals[i];

            bestTemp = bestSum + leftSideMax;
            bestMax = bestMax > bestTemp ? bestTemp : bestMax;
            bestMax = bestMax > bests[i] ? bests[i] : bestMax;

            bestSum = bestSum + totals[i];
            if (bestSum > 0)
            {
                bestSum = rights[i];
            }
        }

        cout << total - bestMax << endl;
    }
    else
    {
        PutLL(0, leftSideMax);
        PutLL(0, rightSideMax);
        PutLL(0, bestMax);
        PutLL(0, total);
        Send(0);
    }


    return 0;
}