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

long long int N;
long long int poczatek, koniec;
long long int suma_fragmentu = 0;
long long int prefiks = 0;
long long int sum_prefiks = 0;
long long int sufiks = 0;
long long int sum_sufiks = 0;
long long int podciag_srodek = 0;
long long int wart_dyn = 0;
int instancja;
long long int statystyki[1000][4];
long long int suma_kanapki = 0;
long long int odpowiedz = 0;
long long int proba = 0;

int main()
{
	N = GetN();
	
	if(N > 50000)
	{
		poczatek = ((long long int)(MyNodeId())*N)/((long long int)(NumberOfNodes()));
		koniec = (((long long int)(MyNodeId())+1)*N)/((long long int)(NumberOfNodes()));
		koniec -= 1;
	
		for(long long int x = poczatek; x <= koniec; x++)
		{
			suma_fragmentu += GetTaste(x);
		
			sum_prefiks += GetTaste(x);
			if(prefiks > sum_prefiks) prefiks = sum_prefiks;
		}
	
		for(long long int x = koniec; x >= poczatek; x--)
		{
			sum_sufiks += GetTaste(x);
			if(sufiks > sum_sufiks) sufiks = sum_sufiks;
		}
	
		for(long long int x = poczatek; x <= koniec; x++)
		{
			if(wart_dyn >= 0) { wart_dyn = GetTaste(x); }
			else { wart_dyn += GetTaste(x); }
		
			if(podciag_srodek > wart_dyn) podciag_srodek = wart_dyn;
		}
	
		if(MyNodeId() > 0)
		{
			PutLL(0, suma_fragmentu);
			PutLL(0, prefiks);
			PutLL(0, sufiks);
			PutLL(0, podciag_srodek);
			Send(0);
		}
	
		else
		{
			for(int i = 1; i < NumberOfNodes(); i++)
			{
				instancja = Receive(-1);
				statystyki[instancja][0] = GetLL(instancja);
				statystyki[instancja][1] = GetLL(instancja);
				statystyki[instancja][2] = GetLL(instancja);
				statystyki[instancja][3] = GetLL(instancja);
			}
		
			statystyki[0][0] = suma_fragmentu;
			statystyki[0][1] = prefiks;
			statystyki[0][2] = sufiks;
			statystyki[0][3] = podciag_srodek;
		
			for(int i = 0; i < NumberOfNodes(); i++) suma_kanapki += statystyki[i][0];
		
			for(int i = 0; i < NumberOfNodes(); i++)
			{
				if(suma_kanapki-statystyki[i][3] > odpowiedz) odpowiedz = suma_kanapki-statystyki[i][3];
			}
		
			if(suma_kanapki > odpowiedz) odpowiedz = suma_kanapki;
		
			for(int a = 0; a < NumberOfNodes(); a++)
			{
				proba = statystyki[a][2];
			
				for(int b = a+1; b < NumberOfNodes(); b++)
				{
					proba += statystyki[b][1];
					if(suma_kanapki-proba > odpowiedz) { odpowiedz = suma_kanapki-proba; }
					proba -= statystyki[b][1];
					proba += statystyki[b][0];
				}
			}
		
			printf("%lld\n", odpowiedz);
		}
	}
	
	else
	{
		if(MyNodeId() == 0)
		{
			for(long long int i = 0; i < N; i++)
			{
				suma_fragmentu += GetTaste(i);
				
				if(wart_dyn >= 0) { wart_dyn = GetTaste(i); }
				else { wart_dyn += GetTaste(i); }
				
				if(podciag_srodek > wart_dyn) podciag_srodek = wart_dyn;
			}
			
			printf("%lld\n", suma_fragmentu-podciag_srodek);
		}
	}
	
	return 0;
}