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
#include "message.h"
#include "kanapka.h"
#include <iostream>
#include <algorithm>
using namespace std;

struct res {
  long long total;
  long long max_l;
  long long max_r;
  long long max_index_l;
  long long max_index_r;
};

int main() {
  long long N = GetN();
  long long numberOfWorkers = min(N, (long long)NumberOfNodes()-1);
  long long work_set = N / numberOfWorkers;
  long long total = 0;
  long long max_l = 0;
  long long max_r = 0;
  long long max_index_l = -1;
  long long max_index_r = -1;
  
  if(MyNodeId() > N) {
	  return 0;
  }
  //cerr << "N:" << N << " N%numberOfWorkers=" << N%numberOfWorkers << " work_set = " << work_set << endl;
  if(MyNodeId()) {
//slaves
    long long poczatek = (MyNodeId()-1) * work_set + ((MyNodeId() - 1 < N%numberOfWorkers) ? (MyNodeId() - 1) : (N%numberOfWorkers));
    long long koniec = poczatek + work_set + (MyNodeId() - 1 < N%numberOfWorkers ? 1 : 0);
	//cerr << "zakres: <" << poczatek << ", " << koniec << ")" << endl;
//left to right
	for(long long i = poczatek; i < koniec; ++i) {
	  //cerr << "N=" << N << ", i=" << i << endl;
	  long long item = GetTaste(i);
	  total += item;
	  if(total > max_l) {
		max_l=total;
		max_index_l=i;
	  }
	}
//right to left
	total = 0;
	for(long long i = koniec - 1; i >= poczatek; --i) {
	  long long item = GetTaste(i);
	  total += item;
	  if(total > max_r) {
		max_r=total;
		max_index_r=i;
	  }
	}

	//cerr << "total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl;
	
	PutLL(0, total);
	PutLL(0, max_l);
	PutLL(0, max_index_l);
	PutLL(0, max_r);
	PutLL(0, max_index_r);
	Send(0);
  } else {
//master
    res * results = new res[numberOfWorkers];
	total = 0;
	max_l = 0;
	for (int i = 0; i < numberOfWorkers; i++) {
      Receive(i + 1);
      results[i].total = GetLL(i + 1);
	  results[i].max_l = GetLL(i + 1);
	  results[i].max_index_l = GetLL(i + 1);
	  results[i].max_r = GetLL(i + 1);
	  results[i].max_index_r = GetLL(i + 1);
	  //left

	  if(results[i].max_l + total > max_l) {
		//cerr << i << ": total=" << results[i].total << " max_l=" << results[i].max_l << endl;
		max_l=results[i].max_l + total;
		//cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
		max_index_l=i;
	  }
	  total+=results[i].total;
	  
	  //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl;
    }
	if(max_index_l < 0) {
		max_l = 0;
		//cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
	}
	//cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
	//right
	total = 0;
	for (int i = numberOfWorkers-1; i > max_index_l; i--) {
	  if(results[i].max_r + total > max_r) {
		//cerr << i << ": total=" << results[i].total << " max_r=" << results[i].max_r << endl;
		max_r=results[i].max_r + total;
		//cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
		max_index_r=i;
	  }
	  total+=results[i].total;
	  
	  //cerr << i + 1 << ": total=" << total << ", max_l[" << max_index_l << "]=" << max_l << ", max_r[" << max_index_r << "]=" << max_r << endl;
    }
	if(max_index_r < 0) {
		max_r = 0;
		//cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
	}

	//last right worker:
	if(max_index_r - max_index_l == 1) {
	  if(results[max_index_l].max_r + total > max_r) {
		  max_r=results[max_index_l].max_r + total;
	  }
	}
	
	cerr << __LINE__ << ": max_l=" << max_l << ", max_r=" << max_r << endl;
	cout << max_l + max_r << endl;
  }
}