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
#include "maklib.h"
#include "message.h"
#include <cstdio>
typedef long long int lld;
lld tab[200];
lld pref[200];
lld suf[200];
lld spref[200];
lld sprz(int a, int b)
{
    if(a>b)return 0;
    if(a==0)return spref[b];
    return spref[b]-spref[a-1];
}
int main()
{
    int n=Size();
    int k=NumberOfNodes();
    
    int m=n/k;
    
    int j=MyNodeId();
    int pocz=j*m+1;
    int kon=(j+1)*m;
    if(j==k-1)kon=n;
    if(n<k)kon=n;
    
    if(n<k && j>0)return 0;
    
    lld aktw=0; lld najl=0;
    lld aktsuf=0; lld nsuf=0;
    lld aktpref=0; lld npref=0;
    lld suma=0;
    for(int i=pocz;i<=kon;i++)
    {
        lld a=(lld)ElementAt(i);
        
        suma+=a;
        
        if(aktw>=0)aktw+=a;
        else aktw=a;
        if(aktw>najl)najl=aktw;
        
        aktpref+=a;
        if(aktpref>npref)npref=aktpref;
    }
    for(int i=kon;i>=pocz;i--)
    {
       lld a=(lld)ElementAt(i);
       aktsuf+=a;
       if(aktsuf>nsuf)nsuf=aktsuf; 
    }
    if(n<k && j==0){printf("%lld\n",najl);return 0;}
    
    if(j>0)
    {
        PutLL(0,najl);
        Send(0);
        PutLL(0,npref);
        Send(0);
        PutLL(0,nsuf);
        Send(0);
        PutLL(0,suma);
        Send(0);
    }
    else
    {
        lld wyn=najl;
        for(int i=1;i<k;i++)
        {
            Receive(i); // najl
            lld kand=GetLL(i);
            if(kand>wyn)wyn=kand;
        }
        //printf("wynik z samych kandydatow to %lld\n",wyn);
        
        pref[0]=npref;
        for(int i=1;i<k;i++)
        {
            Receive(i); // npref
            pref[i]=GetLL(i); 
        }
        
        suf[0]=nsuf;
        for(int i=1;i<k;i++)
        {
            Receive(i); // nsuf
            suf[i]=GetLL(i); 
        }
        
        tab[0]=suma;
        for(int i=1;i<k;i++)
        {
            Receive(i); // suma
            tab[i]=GetLL(i);
        }
        
        spref[0]=tab[0];
        for(int i=1;i<k;i++)spref[i]=spref[i-1]+tab[i];
        
        for(int p=0;p<k;p++)
        {
            for(int q=p+1;q<k;q++)
            {
                lld kand=suf[p]+sprz(p+1,q-1)+pref[q];
                if(kand>wyn)wyn=kand;
            }
        }
        printf("%lld\n",wyn);
    }
    
}