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
//Zamiast szukac najsmaczniejszych czesci po bokach szukamy najmniej szmacznej w srodku. Wynikiem bedzie smacznosc kanapki minus znaleziona czesc.
//Dzielimy kanapke na rowne czesci miedzy jednostki. Kazdy oblicza dla swojego kawalka i przesyla 4 rzeczy: sume, ciag o najmniejszej sumie, prefiks o najmniejszej sumie, sufiks o najmniejszej sumie.
//Sufiks mozna liczyc jednoczesnie z prefiksem, bo sufiks o najmniejszej sumie = suma - prefiks o najwiekszej sumie.
//Laczenie wynikow: albo jest zlaczeniem: prefiks, kilka (byc moze 0) calosci i sufiks albo najmniejsza suma jest wewnatrz jednego kawalka.

#include "kanapka.h"
#include "message.h"
#include <iostream>

using namespace std;

int main()
{
    long long n = GetN();
    int nodes = NumberOfNodes();
    int myid = MyNodeId();
    
    long long from = (long long)myid * n /nodes;
    long long to = (long long)(myid+1) * n /nodes;
    
    long long sum = 0;
    long long maxLeft = -1000*1000*1000-1, minLeft = 0;
    long long minRight = 0;
    long long middle = 0, minMiddle = 0;
    
    
    for (long long i=from; i<to; i++)
    {
        long long val = GetTaste(i);
        sum += val;
        if (minLeft > sum) minLeft = sum;
        if (maxLeft < sum) maxLeft = sum;
        
        if (middle > 0) middle = 0;
        middle += val;
        if (middle < minMiddle)
           minMiddle = middle;
    }
    
    minRight = sum - maxLeft;
    if (minRight > 0) minRight = 0;
    
    PutLL(0, sum);
    PutLL(0, minLeft);
    PutLL(0, minRight);
    PutLL(0, minMiddle);
    Send(0);
    
    long long sumAll = 0;
    long long minVal = 0;
    long long currMin = 0;
    
    if (myid == 0)
    {
        for (int i=0; i<nodes; i++)
        {
            Receive(i);
            long long sumI = GetLL(i);
            long long minLeftI = GetLL(i);
            long long minRightI = GetLL(i);
            long long minMiddleI = GetLL(i); 
            
            sumAll += sumI;
            if (minVal > currMin+minLeftI)
               minVal = currMin+minLeftI;
               
            currMin = min(minRightI, currMin+sumI);
            if (minVal > currMin)
               minVal = currMin;
               
            if (minVal > minMiddleI)
               minVal = minMiddleI;
        }
        
        cout << sumAll - minVal << endl;
    }
}