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

using namespace std;

int main()
{
    long long N, start, stop;
    bool self=false;
    N=GetN();
    if (5*NumberOfNodes()>N) // Gdy liczba wezlow jest porownywalna z N to wezel 0 zrobi cala prace;
    {
        if (MyNodeId()>0) return 0;
        else
        {
            start=0;
            stop=N;
            self=true;
        }
    }
    else
    {
	start=N*MyNodeId()/NumberOfNodes();
	stop=N*(MyNodeId()+1)/NumberOfNodes();
    }
    long long m,p,s,t,x;
    m=p=s=t=GetTaste(start);
    //bazuje na spostrzezeniu ze
    //maksymalna smakowitosc = smakowitosc calkowita - min(0,podciag o najmniejszej sumie)
    //podciag o najmniejszej sumie mozna wyznaczyc poslugujac sie czworkami liczb
    //(m,p,s,t) m- minimalny podciag smakowitosci, p - minimalny prefiks smakowitosci, s - minimalny sufiks smakowitosci, t - calkowita sm
    //majac ww czterokrotki dwoch sasiadujacych ciagow (m1,p1,s1,t1) i (m2,p2,s2,t2) otrzymujemy czterokrotke
    //(m=min(s1+p2,m1,m2) , p=min(p1, t1+p2), s=min (s1+t2, s2), t=t1+t2)
    // krotke inicjuje wartoscia startowa (x,x,x,x)
    for(long long i=start+1; i< stop; i++)
    {
        x=GetTaste(i);
        t=t+x;          //zmienilem kolejnosc przypisan mamy w drugiej krotce m2=p2=s2=t2=x;
        s=min(s+x,x);
        m=min(s,m);
        p=min(p,t);
    }
    if (MyNodeId()>0)
    {
        PutLL(0,m);
        PutLL(0,p);
        PutLL(0,s);
        PutLL(0,t);
        Send(0);
        return 0;

    }
    if (!self)
        for(int i=1; i<NumberOfNodes(); i++)
        {
            long long m2,p2,s2,t2;
			Receive(i);
            m2=GetLL(i);
            p2=GetLL(i);
            s2=GetLL(i);
            t2=GetLL(i);
            m=min(min(s+p2,m),m2);
            p=min(p,t+p2);
            s=min(s+t2,s2);
            t=t+t2;
        }
    long long smak=max(0LL,t-min(0LL,m)); // z calkowitej smakowitosci odejmuje (vel dodaje - dwa minusy) maksymalnie niesmaczne warstwy
                                        // nie zjada kanapki gdy nadal jest niesmaczna
	cout << smak << endl;
    return 0;
}