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
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2014
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Maksymalna podtablica, runda probna
//Czas: O(Size()/NumberOfNodes())
#include "message.h"
#include "maklib.h"

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
#define FOR(x, a, b) for (LL x = (a); x <= (b); x++)
#define PB push_back

LL n = Size(), m = min(Size(), NumberOfNodes()), id = MyNodeId();
		//n - rozmiar tablicy, m - ilosc instancji, id - nr instancji
LL pocz, kon; //dana instancja zajmuje sie fragmentam tablicy od pocz do kon-1

struct T
{
	T() : suma(0), najlepszy(0), lewy(0), prawy(0) {}
	T(LL s, LL n, LL l, LL p) : suma(s), najlepszy(n), lewy(l), prawy(p) {}
	LL suma, najlepszy, lewy, prawy;
};

void policz_fragment(T& f)
{
	FOR(i, pocz, kon-1)
	{
		LL a = ElementAt(i);
		f.prawy = max(0LL, f.prawy) + a;
		f.suma += a;
		f.najlepszy = max(f.najlepszy, f.prawy);
		f.lewy = max(f.lewy, f.suma);
	}
	f.prawy = max(0LL, f.prawy);
}

void wyslij_wiadomosc(const T& f)
{
	PutLL(0, f.suma);
	PutLL(0, f.najlepszy);
	PutLL(0, f.lewy);
	PutLL(0, f.prawy);
	Send(0);
}

void odbierz_wiadomosci(vector<T>& calosc)
{
	FOR(instancja, 1, m-1)
	{
		Receive(instancja);
		LL suma = GetLL(instancja);
		LL najlepszy = GetLL(instancja);
		LL lewy = GetLL(instancja);
		LL prawy = GetLL(instancja);
		calosc.PB(T(suma, najlepszy, lewy, prawy));
	}
}

LL rozwiaz(vector<T>& calosc)
{
	LL najlepszy = 0, prawy = 0;
	FOR(i, 0, m-1)
	{
		T *pom = &calosc[i];
		najlepszy = max(max(najlepszy, pom->najlepszy), prawy + pom->lewy);
		prawy = max(prawy + pom->suma, pom->prawy);
	}
	return najlepszy;
}

void zrob_test()
{
	pocz = (id * n) / m + 1;
	kon = ((id + 1) * n) / m + 1;
	
	T fragment;
	policz_fragment(fragment);
	if (id > 0)
		wyslij_wiadomosc(fragment);
	else
	{
		vector<T> calosc(1, fragment);
		odbierz_wiadomosci(calosc);
		cout << rozwiaz(calosc) << '\n';
	}
}

int main()
{
	if (id < m)
		zrob_test();
	return 0;
}