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

#include<iostream>

using namespace std;
typedef long long ll;

int main()
{
    ll i, a, b, sum, maxl, maxr, x, *cl, in;
    ll id = MyNodeId();
    ll n = GetN();
    ll d = NumberOfNodes();
    a = id*n;
    a/=d;
    b=(id+1)*n;
    b/=d;
    sum=0;
    maxl=0;
    maxr=0;
    in=0;
    cl = new ll[b-a+1];
    for(i=a; i < b; i++)
    {
        x = GetTaste(i);
        sum+=x;
        if(sum > maxl)
            maxl = sum;
        cl[i-a]=maxl;
    }
    in = sum;
    sum=0;
    for(i=b-1; i >= a; i--)
    {
        x = GetTaste(i);
        sum+=x;
        if(sum > maxr)
            maxr = sum;
        if(i > a && cl[i-1-a]+maxr > in)
            in = cl[i-1-a]+maxr;
    }
    if(id==0)
    {
        ll *left, *right, *all, *ins;
        left = new ll[d];
        right = new ll[d];
        all = new ll[d];
        ins = new ll[d];
        left[0]=maxl;
        right[0]=maxr;
        all[0]=sum;
        ins [0]=in;
        for(i=1; i < d; i++)
        {
            all[i]=GetLL(i);
            left[i]=GetLL(i);
            right[i]=GetLL(i);
            ins[i] = GetLL(i);
        }
        ll *pref, *suf, *bl, *br;
        pref = new ll[d];
        suf = new ll[d];
        bl = new ll[d];
        br = new ll[d];

        pref[0]=0;
        bl[0]=left[0];
        for(i=1; i < d; i++)
        {
            pref[i] = pref[i-1] + all[i-1];
            bl[i]=max(bl[i-1], pref[i]+left[i]);
        }
        suf[d-1]=0;
        br[d-1] = right[d-1];
        for(i=d-2; i>=0; i--)
        {
            suf[i]=suf[i+1] + all[i+1];
            br[i]=max(br[i+1], suf[i]+right[i]);
        }
        ll wynik=0, w=0, z;
        for(i=0; i < d-1; i++)
        {
            w=pref[i]+suf[i]+ins[i];
            z=bl[i] + br[i+1];
            if(wynik < w)
                wynik = w;
            if(wynik < z)
                wynik = z;
        }
        cout << wynik;
    }
    else
    {
        PutLL(0, sum);
        PutLL(0, maxl);
        PutLL(0, maxr);
        PutLL(0, in);
    }

    return 0;
}