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
#include"kanapka.h"
#include<message.h>
#include<iostream>
#include<algorithm>
#include<limits>
using namespace std;
struct worst
{
    worst(){}
    worst(long long a, long long b, long long c, long long d): worstSuffix(a) , worstPrefix(b), worstAll(c), worstPart(d)
    {

    }
    long long worstSuffix;
    long long worstPrefix;
    long long worstAll;
    long long worstPart;
};
int main()
{
    long long n = GetN();
    if(MyNodeId() >=n) return 0;
    const long long inf = std::numeric_limits<long long>::max();
    int computers = std::min(n,(long long)NumberOfNodes());
    long long worstSuffix = inf, worstPrefix = inf, worstAll = inf, worstPart = inf;
    int ile = n/computers;
    long long * tab = new long long[n/computers + 3];
    int begin = MyNodeId()*ile;
    int end = (MyNodeId() != computers-1) ? begin + ile : n; 
    tab[0]= GetTaste(begin);
    for (int i=begin+1;i<end;i++)
    {
	tab[i-begin] = tab[i-1-begin] + GetTaste(i);
    }
    worstAll= tab[end-1-begin];worstSuffix = tab[end-1-begin];
    for (int i = 0 ;i<end-begin;i++)
    {
	if(tab[i] < worstPrefix) worstPrefix = tab[i];
	if(i!=end-begin-1)
	if(tab[end-1-begin]-tab[i] < worstSuffix) worstSuffix = tab[end-1-begin] - tab[i];
    }
    worstPart=GetTaste(begin);long long  tmp = worstPart;
    for (int i  = begin+1;i<end;i++)
    {
	if(GetTaste(i) < worstPart) worstPart = GetTaste(i);
	tmp+=GetTaste(i);
	if(tmp> 0 ) tmp=0;
	else
	   if(tmp<worstPart) worstPart =tmp;
    }

   
    if(MyNodeId()>0)
    {
    	PutLL(0,worstAll);
    	PutLL(0,worstPrefix);
   	 PutLL(0,worstSuffix);
    	PutLL(0,worstPart);
    	Send(0);
    }



    if(MyNodeId()==0)
    {

    	worst * t = new worst[computers];
	t[0] = worst(worstSuffix,worstPrefix,worstAll,worstPart);
	for (int i =1;i<computers;i++)
	{

	    Receive(i);
	    long long  worstAll2 = GetLL(i);
	    long long worstPrefix2 = GetLL(i);
	    long long worstSuffix2 = GetLL(i);
	    long long worstPart2 = GetLL(i);

	    t[i] = worst(worstSuffix2,  worstPrefix2, worstAll2, worstPart2);
	}
       long long best=inf,sum=0;	
	for (int i =0;i<computers;i++)
	{

	    sum+=t[i].worstAll;
	    if(t[i].worstPart< best) best=t[i].worstPart;
	}
	long long sums[computers];
	sums[0]=0;
	for (int i =0;i<computers;i++)
	{
	    sums[i+1] = sums[i]+ t[i].worstAll;
	}
	for (int i = 0;i<computers;i++)
	{
	    for (int j=i+1;j<computers;j++)
	    {
		long long tmp = t[i].worstSuffix + t[j].worstPrefix;
		
		if(j>i+1)
		{
		    tmp+=sums[j] - sums[i+1];
		}
		if(tmp<best) best=tmp; 
	    }
	}
	printf("%lld\n",sum-best);


	delete [] t;
    }



    delete [] tab;


}