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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include "kanapka.h"
#include "message.h"

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    if (MyNodeId() == 0)
    {
        //long long int sumy[NumberOfNodes()];
        vector<long long int> sumy(NumberOfNodes());
        vector<long long int> min_c(NumberOfNodes());
        vector<long long int> min_p(NumberOfNodes());
        vector<long long int> min_s(NumberOfNodes());

        long long int sum_all = 0;
        long long int min_ac = 0;

        long long int w = 0;
        long long int w_p = 0;
        long long int wyn = 0;

        int pom;

        // Dla 0 - odbieranie wiadomosci od wszystkich, przeszukiwanie i ustalanie wyniku
        for (int i = 1; i < NumberOfNodes(); i++)
        {
            Receive(i);
            pom = GetInt(i);
            if (pom != 0)
            {
                sumy[i] = GetLL(i);
                min_c[i] = GetLL(i);
                min_p[i] = GetLL(i);
                min_s[i] = GetLL(i);

                sum_all += sumy[i];

                if (min_c[i] < min_ac)
                    min_ac = min_c[i];

                w_p = w + min_p[i];

                if (w < 0)
                    w += sumy[i];
                else
                    w = min_s[i];

                if (w_p < wyn)
                    wyn = w_p;

                if (w < wyn)
                    wyn = w;
                }
        }

        if (min_ac < wyn)
            wyn = min_ac;

        cout << sum_all - wyn;
    }
    else
    {
        int ile_dziel = NumberOfNodes() - 1;
        if (GetN() < NumberOfNodes())
            ile_dziel = GetN() - 1;

        // Podzial dlugosci na rowne czesci
        long long int dl_czesci = GetN() / (ile_dziel);
        long long int start = (MyNodeId() - 1) * dl_czesci; // poczatek
        long long int koniec = start + dl_czesci;
        if (MyNodeId() == ile_dziel) //ostatni bierze do konca kanapki
            koniec = GetN();

        if (MyNodeId() > ile_dziel)
        {
            PutInt(0, 0);
            Send(0);
            return 0;
        }

        // Obliczanie: #sumaryczny smak #minimalny smak ciagly #minimalny prefix #minimalny sufix
        long long int c_min = 0, wyn_min = 0;
        long long int pre_max = 0, wyn_pre_max = 0;
        long long int sum = 0;
        long long int pre_min = 0;
        bool kpmin = false;
        bool kpmax = false;
        long long int su_min = 0;
        for (long long int i = start; i < koniec; i++)
        {
            // suma
            sum += GetTaste(i);

            //minimalny podciag i minimalny prefix
            if (c_min <= 0)
                c_min += GetTaste(i);
            else
            {
                c_min = GetTaste(i);
                kpmin = true;
            }

            if (c_min < wyn_min)
            {
                wyn_min = c_min;
                if (!kpmin)
                    pre_min = c_min;
            }

            // maksymalny prefix - do okreslenia minimalnego sufixu
            if (!kpmax)
            {
                if (pre_max >= 0)
                {
                    pre_max += GetTaste(i);
                    if (pre_max >= wyn_pre_max)
                        wyn_pre_max = pre_max;
                }
                else
                    kpmax = true;
            }
        }
        su_min = sum - wyn_pre_max;
        PutInt(0, 1);
        PutLL(0, sum);
        PutLL(0, wyn_min);
        PutLL(0, pre_min);
        PutLL(0, su_min);
        Send(0);
    }
    return 0;
}