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
//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;                                        
    }                                                                           
}