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

long long int max(long long int a,long long int b)
{
	return (a>b)?a:b;
}

int main()
{
	long long int pocz,kon,ID,Nod;
	long long int N;
	N=GetN();
	Nod=NumberOfNodes();
	ID=MyNodeId();
	pocz=N*ID/Nod;
	kon=N*(ID+1)/Nod;
	long long int ileel=kon-pocz;
	long long int * najzp;
	long long int * sumy;
	najzp=(long long int *) malloc(sizeof(long long int)*(ileel+2));
	sumy=(long long int *) malloc(sizeof(long long int)*(ileel+2));
	sumy[0]=0;
	najzp[ileel+1]=0;
	long long int suma=0,a,zlew=0,zpraw=0,zobu=0,razem,tmp;
	for (long long int i=pocz;i<kon;i++)
	{
		a=GetTaste(i);
		suma+=a;
		sumy[i-pocz+1]=suma;
		if (suma>zlew) zlew=suma;
	}
	razem=suma;
	for (long long int i=ileel;i>0;i--)
	{
		tmp=razem-sumy[i-1];
		if (tmp>zpraw) zpraw=tmp;
		najzp[i]=zpraw;
	}
	for (long long int i=0;i<=ileel;i++)
	{
		tmp=sumy[i]+najzp[i+1];
		if (tmp>zobu) zobu=tmp;
	}
	free(najzp);
	free(sumy);
	long long int zlew2=0,zpraw2=0,zobu2=0,razem2;
	//-------------------------------------------------------------
	int kto;
	for (int podz=1;podz<Nod;podz*=2)
	{
		if (ID%(2*podz)!=0)
		{
			kto=(ID-podz);
			PutLL(kto,zlew);
			PutLL(kto,zpraw);
			PutLL(kto,zobu);
			PutLL(kto,razem);
			Send(kto);
			return 0;
		} else
		{
			kto=(ID+podz);
			if (kto>=Nod) continue;
			Receive(kto);
			zlew2=GetLL(kto);
			zpraw2=GetLL(kto);
			zobu2=GetLL(kto);
			razem2=GetLL(kto);
			zobu=max(max(zlew+zpraw2,razem+zobu2),razem2+zobu);
			zlew=max(zlew,razem+zlew2);
			zpraw=max(zpraw2,razem2+zpraw);
			razem=razem+razem2;
		}
	}
	if (ID==0) printf("%lld\n",zobu);
	return 0;
	
}