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
#include "kanapka.h"
#include"message.h"
#include <algorithm>
#include <iostream>
#include<vector>
#include<cstdio>
#define min(a,b) ((a)>(b)?(b):(a))
#define ALL(u) (u).begin(),(u).end()
using namespace std;
typedef long long LL;
#define PB push_back
int main() {
    long long i,N = GetN();
    int p=MyNodeId();
    int non=NumberOfNodes();
    long long l,r,a,lr;
    long long b=N*p/non,e=N*(p+1)/non;
    vector<long long> t(e-b+1),u(e-b+1),v(e-b+1);
    for(i=b;i<e;++i)
    {
        t[i-b+1]=GetTaste(i)+t[i-b];
    }
    u[e-b]=a=t[e-b];
    for(i=e-b-1;i>=0;--i)
    {
        u[i]=min(u[i+1],t[i]);
    }
    for(i=1;i<=e-b;++i)
        t[i]=max(t[i-1],t[i]);
    for(i=0;i<=e-b;++i)
        v[i]=t[i]-u[i];
    l=t[e-b];
    r=a-u[0];
    lr=a+*max_element(ALL(v));
   // printf("%lld %lld %lld %lld\n",a,l,r,lr);
    if(p)
    {
        PutLL(0,a);
        PutLL(0,l);
        PutLL(0,r);
        PutLL(0,lr);
        Send(0);
    }
    else
    {
        vector<LL> ta(non+1,0),tl(non,l),tr(non,r),tx(non,lr);
        ta[1]=a;
        for(i=1;i<non;++i)
        {
            Receive(i);
            ta[i+1]=GetLL(i)+ta[i];
            tl[i]=GetLL(i);
            tr[i]=GetLL(i);
            tx[i]=GetLL(i);
        }
        long long m=0,n;
        int j;
        for(i=0;i<non;++i)
            for(j=i+1;j<non;++j)
            {
                n=ta[non]-ta[j+1]+ta[i]+tl[i]+tr[j];
                m=max(n,m);
            }
        for(i=0;i<non;++i)
        {
            n=ta[non]-ta[i+1]+ta[i]+tx[i];
            m=max(m,n);
        }
        printf("%lld",m);
    }
  return 0;
}