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 <algorithm>
#include <iostream>

typedef long long ll;

int main() {
  int noOfNodes = NumberOfNodes();
  ll N = GetN();
    
  ll basicChunkSize = N/noOfNodes;
  ll myBeg, myEnd;
  
  ll myId = MyNodeId();
  bool computeOnAllNodes = true;
  if(N < noOfNodes) {
    computeOnAllNodes = false;
    if(myId == 0) { 
      myBeg = 0;
      myEnd = N - 1;
    } else {
      return 0;
    }
  } else {
    myBeg = myId * basicChunkSize + std::min(N % noOfNodes, myId);
    myEnd = myBeg + basicChunkSize + (myId < N % noOfNodes ? 1 : 0) - 1;
  }
  //std::cout << myId << ": " << myBeg << "-" << myEnd << std::endl;

  ll mySum = 0;
  ll localMinSum = 0;
  ll minSumFromMyBeg = 0;
  ll maxSumFromMyBeg = 0;
  
  for(ll i = myBeg; i <= myEnd; i++) {
    ll taste = GetTaste(i);
    mySum += taste;
    localMinSum = std::min(localMinSum, mySum - maxSumFromMyBeg);
    maxSumFromMyBeg = std::max(maxSumFromMyBeg, mySum);
    minSumFromMyBeg = std::min(minSumFromMyBeg, mySum);    
    //std::cout << "maxSumFromMyBeg: " << maxSumFromMyBeg << "\n";
    //std::cout << "minSumFromMyBeg: " << minSumFromMyBeg << "\n";
  }
  
  ll globalSum, globalMinSum;
  if(myId == 0) {
    globalSum = mySum;
    globalMinSum = localMinSum;
  }
    
  ll prevSum = mySum;
  ll prevMax = maxSumFromMyBeg;
  
  if(computeOnAllNodes == true) {
    if(myId == 0) {
      ll maxSumFromBeg = maxSumFromMyBeg;
      for(int i = 1; i < noOfNodes; i++) {
        PutLL(i, globalSum);
        PutLL(i, maxSumFromBeg);
        Send(i);

        Receive(i);
        ll mySumi = GetLL(i);
        //ll localMinSumi = GetLL(i);
        ll maxSumFromMyBegi = GetLL(i);

        //globalMinSum = std::min(globalMinSum, localMinSumi);
        maxSumFromBeg = std::max(maxSumFromBeg, globalSum + maxSumFromMyBegi);
        globalSum += mySumi;
        
        Receive(i);
        ll localMinSumi = GetLL(i);
        globalMinSum = std::min(globalMinSum, localMinSumi);
      }
    } else {
      Receive(0);
      prevSum = GetLL(0);
      prevMax = GetLL(0);
      
      //std::cout << "prevSum: " << prevSum << "\n";
      //std::cout << "prevMax: " << prevMax << "\n";
      
      PutLL(0, mySum);
      //PutLL(0, localMinSum);
      PutLL(0, maxSumFromMyBeg);
      Send(0);
      
      localMinSum = std::min(localMinSum, prevSum + minSumFromMyBeg - prevMax);
      //std::cout << "localMinSum: " << localMinSum << "\n";
      PutLL(0, localMinSum);
      Send(0);
    }
  }
  
  if(myId == 0) {
    //std::cout << "globalSum: " << globalSum << "\n";
    ll bestTaste = globalSum - globalMinSum;
    std::cout << bestTaste << "\n";
  }
  
  return 0;
}