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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#include "kanapka.h"
#include "message.h"

using namespace std;

struct Job {
  long long m_id = -1LL;

  long long m_begin = 0LL;
  long long m_end = 0LL;

  long long m_sum = 0LL;
  long long m_best = 0LL;
  long long m_best_left = 0LL;
  long long m_best_right = 0LL;

  Job(long long id = -1LL, long long begin = -1LL, long long end = -1LL)
      : m_id(id), m_begin(begin), m_end(end) {}
};

void sendJob(int target, const Job &job) {
  PutLL(target, job.m_id);
  PutLL(target, job.m_begin);
  PutLL(target, job.m_end);
  PutLL(target, job.m_sum);
  PutLL(target, job.m_best);
  PutLL(target, job.m_best_left);
  PutLL(target, job.m_best_right);
  Send(target);
}

int receiveJob(int source, Job &job) {
  source = Receive(source);
  job.m_id = GetLL(source);
  job.m_begin = GetLL(source);
  job.m_end = GetLL(source);
  job.m_sum = GetLL(source);
  job.m_best = GetLL(source);
  job.m_best_left = GetLL(source);
  job.m_best_right = GetLL(source);

  return source;
}

class Master {
 private:
  static const long long MAX_JOB_SIZE = 1000000;

  int m_id = 0;

  std::vector<Job> m_jobs;

  long long m_num_workers;
  long long m_num_pieces;

  std::vector<long long> m_best_left;
  std::vector<long long> m_best_right;
  std::vector<long long> m_sums;

 public:
  explicit Master()
      : m_id(MyNodeId()),
        m_num_workers(NumberOfNodes() - 1),
        m_num_pieces(GetN()) {}

  void run() {
    // If this process is not be the master - stop
    if (m_id != m_num_workers) {
      return;
    }
    prepare_jobs();
    run_jobs();
    aggregate();
  }

 private:
  void prepare_jobs() {
    // Create jobs for the workers
    Job job = {0LL, 0LL, 0LL};
    do {
      job.m_id = m_jobs.size();
      job.m_begin = job.m_end;
      job.m_end = std::min(m_num_pieces, job.m_begin + MAX_JOB_SIZE);
      m_jobs.push_back(job);
    } while (job.m_end < m_num_pieces);
  }

  void run_jobs() {
    // Initial distribution
    std::size_t job_id = 0;
    for (; job_id < m_jobs.size() && job_id < m_num_workers; ++job_id) {
      // Send a job to the worker
      sendJob(job_id, m_jobs[job_id]);
    }
    // Some workers could be jobless - let them know
    for (std::size_t i = job_id; i < m_num_workers; ++i) {
      // Send empty job
      sendJob(i, Job());
    }

    // Wait for answers for all the jobs and distribute any undone ones
    std::size_t num_rec = 0;
    for (; num_rec < m_jobs.size(); ++num_rec) {
      Job job;
      // Wait for a response from any worker
      int source = receiveJob(-1, job);

      m_jobs[job.m_id] = job;

      // If any jobs left undone - ask the worker to perform the next
      if (job_id < m_jobs.size()) {
        sendJob(source, m_jobs[job_id++]);
      }
      // Otherwise notify that no job is left
      else {
        // Send empty job
        sendJob(source, Job());
      }
    }
  }

  void aggregate() {
    // Shifted by 1 for easier coding
    std::vector<long long> best_left(m_jobs.size() + 1);
    std::vector<long long> sum_left(m_jobs.size() + 1);
    best_left[0] = 0LL;
    sum_left[0] = 0LL;
    for (std::size_t i = 1; i < m_jobs.size(); ++i) {
      // Shifted by 1
      best_left[i] = std::max(best_left[i - 1],
                              sum_left[i - 1] + m_jobs[i - 1].m_best_left);
      sum_left[i] += sum_left[i - 1] + m_jobs[i - 1].m_sum;
    }

    long long best_right = 0LL;
    long long sum_right = 0LL;
    long long best = 0LL;
    // Run through all the elements (no special case thanks to the shift above)
    for (long long i = m_jobs.size() - 1; i >= 0; --i) {
      best_right = std::max(best_right, sum_right + m_jobs[i].m_best_right);
      // Check the sum of best to the left of this job
      // and the best to the right including this job
      best = std::max(best, best_right + best_left[i]);
      // Check taking both ends until this job and the best of this job
      best = std::max(best, sum_left[i] + m_jobs[i].m_best + sum_right);
      sum_right += m_jobs[i].m_sum;
    }
    std::cout << best << std::endl;
  }
};

class Worker {
 private:
  int m_id = 0;
  int m_master_id = 0;

  std::vector<long long> m_bests_left;

 public:
  explicit Worker() : m_id(MyNodeId()), m_master_id(NumberOfNodes() - 1) {}

  void run() {
    // If this process is the master - stop
    if (m_id == m_master_id) {
      return;
    }

    // Start  processing jobs
    Job job;
    do {
      // Receive a job
      receiveJob(m_master_id, job);
    } while (process_job(job));
  }

 private:
  bool process_job(Job &job) {
    if (job.m_id < 0) {
      return false;
    }

    job.m_sum = 0LL;
    // Best result starting from both sides
    job.m_best = 0LL;
    // Best result starting from left only
    job.m_best_left = 0LL;
    // Best result starting from right only
    job.m_best_right = 0LL;

    // Shifted by one element for easier coding
    m_bests_left.resize(job.m_end - job.m_begin + 1);
    m_bests_left[0] = 0LL;
    // Compute the sum and best left
    for (long long i = job.m_begin; i < job.m_end; ++i) {
      job.m_sum += GetTaste(i);
      job.m_best_left = std::max(job.m_best_left, job.m_sum);
      // Shifted ahead by one
      m_bests_left[i - job.m_begin + 1] = job.m_best_left;
    }
    // Compute the best right and total best
    job.m_sum = 0LL;
    // Run for all elements - thanks to the shift
    for (long long i = job.m_end - 1; i >= job.m_begin; --i) {
      job.m_sum += GetTaste(i);
      job.m_best_right = std::max(job.m_best_right, job.m_sum);
      job.m_best = std::max(job.m_best,
                            job.m_best_right + m_bests_left[i - job.m_begin]);
      std::cout.flush();
    }

    // Send back the result
    sendJob(m_master_id, job);

    return true;
  }
};

int main() {
  Master master;
  Worker worker;

  master.run();
  worker.run();

  return 0;
}