#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; }
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; } |