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

#include <cstring>
#include <cstdio>
#include <algorithm>

#define MAX_BLK 1000000

using namespace std;

void recv_data( int src, void *buf, size_t size ) {
    int *s = (int*)buf;
    for ( int i=0; i<size/4; i++ ) {
        s[i] = GetInt( src );
    }
}

#define recv_struct( src, s ) recv_data( src, (void*)&s, sizeof(s) )

void send_data( int dst, void *buf, size_t size ) {
    int *s = (int*)buf;
    for ( int i=0; i<size/4; i++ ) {
        PutInt( dst, s[i] );
    }
    Send(dst);
}

#define send_struct( dst, s ) send_data( dst, (void*)&s, sizeof(s) )

typedef struct {
    long long s;
    long long l,r;
    long long m;
} segment_info;

void segment_info_calc( segment_info *s, int b, int n ) {
    memset( s, 0, sizeof(*s) );
    long long *_L = new long long[ n ];
    for ( int i=0; i<n; i++ ) {
        _L[i] = s->l;
        s->s += GetTaste(b+i);
        s->l = max( s->l, s->s );
    }
    s->s = 0;
    for ( int i=n-1; i>=0; i-- ) {
        s->s += GetTaste(b+i);
        s->r = max( s->r, s->s );
        s->m = max( s->m, s->r + _L[i] );
    }
    delete _L;
}

int main() {
  int n = GetN();
  int inst_count = NumberOfNodes();
  int inst = MyNodeId();
  int b_per_inst = n / MAX_BLK / inst_count + 1;

  int b_count = inst_count * b_per_inst;
  int b_beg = inst * b_per_inst;

  for ( int i=0; i<b_per_inst; i++ ) {
      int b = ((long long)n)*(b_beg+i)/b_count;
      int e = ((long long)n)*(b_beg+i+1)/b_count;

      segment_info seg;
      segment_info_calc( &seg, b, max(e-b,0) );
      send_struct(0,seg);
  }

  if ( inst == 0 ) {
      segment_info *s = new segment_info[ inst_count * b_per_inst ];
      int *nb = new int[ b_count ];
      memset( nb, 0, sizeof(*nb) * b_count );
      for ( int i=0; i<b_count; i++ ) {
          int a = Receive( -1 );
          recv_struct( a, s[a*b_per_inst + (nb[a]++)] );
      }
      delete nb;

      long long sum=0,l=0,r=0,w=0,_s=0;
      long long *_L = new long long[ b_count ];
      for ( int i=0; i<b_count; i++ ) sum+=s[i].s;
      for ( int i=0; i<b_count; i++ ) {
          w = max( w, sum-s[i].s+s[i].m );
          _L[i]=l;
          l = max( l, _s+s[i].l );
          _s += s[i].s;
      }
      _s = 0;
      for ( int i=b_count-1; i>=0; i-- ) {
          r = max( r, _s+s[i].r );
          w = max( w, _L[i]+r );
          _s += s[i].s;
      }

      delete _L;
      delete s;
      printf("%lld\n",w);
  }

  return 0;
}