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

#include <algorithm>
#include <iostream>

//#include <x86intrin.h>

using namespace std;

/* structure must be 8bit-aligned!!!! */
void struct_send( int target, long long *_s, int size )
{
   while ( size-- )
	 PutLL( target, *(_s++) );
   Send( target );
}

/* structure must be 8bit-aligned!!!! */
void struct_recv( int target, long long *_s, int size )
{
   Receive( target );
   while ( size-- )
	  *(_s++) = GetLL( target );
}

/* structure must be 8bit-aligned!!!! */
#define send( tt, s ) struct_send( tt, ( long long * )&s, sizeof( s )/8 );
#define recv( tt, s ) struct_recv( tt, ( long long * )&s, sizeof( s )/8 );

struct calc_data
{
  long long sum;
  long long mx_sum;
  long long mx_left;
  long long mx_right;
};

int n;
int node;
int num_nodes;

void sum_results()
{
  long long wyn = 0;
  long long akt_sum = 0;
  
  struct calc_data c;
  
  for ( int i=0; i<num_nodes; i++ )
      {
	recv( i, c );
	
	wyn = max( wyn, c.mx_sum );
	wyn = max( wyn, akt_sum+c.mx_left );
	
	akt_sum += c.sum;
	if ( akt_sum < 0 )
	   akt_sum = c.mx_right;
      }
  
  printf( "%lld\n", wyn );
}

int main()
{
/*#ifdef __SSE__
  {
    volatile __m128 a;
    volatile __m128 b;
    volatile __m128 c = _mm_add_ps( a, b );
    printf( "%f %f %f %f\n", ((float*)&c)[0], ((float*)&c)[1], ((float*)&c)[2], ((float*)&c)[3] );
  }
#endif*/
  
   n = Size();
   node = MyNodeId();
   num_nodes = NumberOfNodes();
   
   struct calc_data c = { 0, 0, 0, 0 };
   
   int first = (n/num_nodes)*node+1;
   int last  = (n/num_nodes)*(node+1);
   if ( node == num_nodes-1 ) last=n;
   
   long long akt_sum = 0;
   
   for ( int i=first; i<=last; i++ )
      {
	int a = ElementAt( i );
	
	c.sum += a;
	c.mx_left = max( c.mx_left, c.sum );
	
	akt_sum += a;
	if ( akt_sum < 0 )
	   akt_sum = 0;
	c.mx_sum = max( c.mx_sum, akt_sum );
      }
   
   long long right_sum = 0;
   
   for ( int i=last; i>=first; i-- )
       {
	 int a = ElementAt( i );
	 
	 right_sum += a;
	 c.mx_right = max( c.mx_right, right_sum );
       }
   
   send( 0, c );
   
   if ( !node )
      sum_results(  );
   
   return 0;
}