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

using namespace std;
int non, mni;
long long int N;
long long int t;

long long int poczatek, koniec;

long long int sum, pref, suf, hole;

long long int *SUM, *PREF, *SUF, *HOLE;

long long result = 0 ;

int main()
{
    non = NumberOfNodes();
    mni = MyNodeId();

    N = GetN();

    poczatek = mni*(N/non);
    if( mni<non-1 )
        koniec = (mni+1)*(N/non)-1;
    else
        koniec = N-1;

    sum=pref=suf=hole=0;
    long long int minPref=0;
    long long int maxHole=0;
    for( long long int i=poczatek ; i<=koniec ; i++ )
    {
        t = GetTaste(i);

        sum += t;
        if( pref<sum )
            pref=sum;
        if( minPref>sum )
            minPref=sum;

        if( pref-sum > maxHole )
            maxHole=pref-sum;
    }
    suf = sum-minPref;
    hole = sum+maxHole;

    if( mni>0 )
    {
        PutLL(0, sum);
        PutLL(0, pref);
        PutLL(0, suf);
        PutLL(0, hole);
        Send(0);
        return 0;
    }

    SUM = new long long int [non];
    SUM[0]=sum;
    PREF = new long long int [non];
    PREF[0]=pref;
    SUF = new long long int [non];
    SUF[0] = suf;
    HOLE = new long long int [non];
    HOLE[0] = hole;

    for( int i=1 ; i<non ; i++ )
    {
        Receive(i);
        SUM[i]=GetLL(i);
        PREF[i]=GetLL(i);
        SUF[i]=GetLL(i);
        HOLE[i]=GetLL(i);
        sum += SUM[i];
    }

    long long int s=0;
    for( int i=1 ; i<non ; i++ )
    {
        s += SUM[i-1];
        PREF[i] += s;
    }
    s=0;
    for( int i=non-2 ; i>=0 ; i-- )
    {
        s += SUM[i+1];
        SUF[i] += s;
    }

    for( int i=0 ; i<non ; i++ )
    for( int j=i+1 ; j<non ; j++ )
    {
        if( result<PREF[i]+SUF[j] )
            result = PREF[i]+SUF[j];
    }

    for( int i=0 ; i<non ; i++ )
    {
        if( result<sum-SUM[i]+HOLE[i])
            result = sum-SUM[i]+HOLE[i];
    }
    printf("%lld\n", result);

    return 0;
}