#include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; #define REP(x,n) for(int x=0;x<(n);++x) #define FOR(a,b,e) for(int a=(b); a<=(e);++a) #define FORD(a,b,e) for(int a=(b); a>=(e);--a) long long T1[10000002]; void doWork(long long N, int nodes, int myId) { long long ToSend[4]; /// suma, prefiks, sufiks, prefikso-sufiks long long myStart = N*myId / nodes; long long myEnd = N*(myId+1) / nodes - 1; long long sumAll = 0; FOR(i, myStart, myEnd) { sumAll += GetTaste(i); T1[i-myStart+1] = max(T1[i-myStart], sumAll); #ifdef _HOMEDEBUG cout << i << ": " << sumAll << " " << T1[i-myStart+1] << endl; #endif } ToSend[0] = sumAll; ToSend[1] = T1[myEnd-myStart+1]; sumAll = 0; long long T2 = 0; long long maxWyn = 0; FORD(i, myEnd, myStart) { sumAll += GetTaste(i); T2 = max(T2, sumAll); maxWyn = max(maxWyn, T2+T1[i-myStart]); #ifdef _HOMEDEBUG cout << i << ": " << sumAll << " " << T2 << " " << maxWyn << endl; #endif } ToSend[2] = T2; ToSend[3] = maxWyn; REP(i, 4) { PutLL(0, ToSend[i]); #ifdef _HOMEDEBUG cout << "send " << ToSend[i] << endl; #endif } Send(0); } void generateOutput(int nodes) { vector<long long> ranges(nodes); vector<long long> maxPref(nodes); vector<long long> maxSuf(nodes); vector<long long> maxPrefSuf(nodes); REP(i, nodes) { Receive(i); ranges[i] = GetLL(i); maxPref[i] = GetLL(i); maxSuf[i] = GetLL(i); maxPrefSuf[i] = GetLL(i); } vector<long long> T3(nodes+1, 0), sumBeg(nodes+1, 0); FOR(i, 0, nodes-1) { T3[i+1] = max(T3[i], sumBeg[i]+maxPref[i]); sumBeg[i+1] = sumBeg[i] + ranges[i]; #ifdef _HOMEDEBUG cout << i << "-3 " << T3[i+1] << " " << sumBeg[i+1] << endl; #endif } vector<long long> T4(nodes+1, 0), sumEnd(nodes+1, 0); FORD(i, nodes-1, 0) { T4[i] = max(T4[i+1], sumEnd[i+1]+maxSuf[i]); sumEnd[i] = sumEnd[i+1] + ranges[i]; #ifdef _HOMEDEBUG cout << i << "-4 " << T4[i] << " " << sumEnd[i] << endl; #endif } #ifdef _HOMEDEBUG cout << "T3\tT4\tPrefSuf" << endl; REP(x, nodes+1) cout << T3[x] << "\t" << T4[x] << "\t" << maxPrefSuf[x] << endl; #endif long long totalMax = 0; #ifdef _HOMEDEBUG cout << "totalMax" << endl; #endif REP(i, nodes) { long long m1 = T3[i]+T4[i], m2 = sumBeg[i]+sumEnd[i+1]+maxPrefSuf[i]; totalMax = max(totalMax, max(m1, m2)); #ifdef _HOMEDEBUG cout << m1 << " " << m2 << " -> " << totalMax << endl; #endif } cout << totalMax; } int main() { #if defined(_HOMEDEBUG) || defined(_HOMEDEBUG1) GetN(); int instances = 100; REP(x, instances) { WORKING_THREAD(x); doWork(GetN(), instances, x); } WORKING_THREAD(0); generateOutput(instances); #else int nodes = NumberOfNodes(); int myId = MyNodeId(); doWork(GetN(), nodes, myId); if(myId == 0) generateOutput(nodes); #endif return 0; }
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 | #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> using namespace std; #define REP(x,n) for(int x=0;x<(n);++x) #define FOR(a,b,e) for(int a=(b); a<=(e);++a) #define FORD(a,b,e) for(int a=(b); a>=(e);--a) long long T1[10000002]; void doWork(long long N, int nodes, int myId) { long long ToSend[4]; /// suma, prefiks, sufiks, prefikso-sufiks long long myStart = N*myId / nodes; long long myEnd = N*(myId+1) / nodes - 1; long long sumAll = 0; FOR(i, myStart, myEnd) { sumAll += GetTaste(i); T1[i-myStart+1] = max(T1[i-myStart], sumAll); #ifdef _HOMEDEBUG cout << i << ": " << sumAll << " " << T1[i-myStart+1] << endl; #endif } ToSend[0] = sumAll; ToSend[1] = T1[myEnd-myStart+1]; sumAll = 0; long long T2 = 0; long long maxWyn = 0; FORD(i, myEnd, myStart) { sumAll += GetTaste(i); T2 = max(T2, sumAll); maxWyn = max(maxWyn, T2+T1[i-myStart]); #ifdef _HOMEDEBUG cout << i << ": " << sumAll << " " << T2 << " " << maxWyn << endl; #endif } ToSend[2] = T2; ToSend[3] = maxWyn; REP(i, 4) { PutLL(0, ToSend[i]); #ifdef _HOMEDEBUG cout << "send " << ToSend[i] << endl; #endif } Send(0); } void generateOutput(int nodes) { vector<long long> ranges(nodes); vector<long long> maxPref(nodes); vector<long long> maxSuf(nodes); vector<long long> maxPrefSuf(nodes); REP(i, nodes) { Receive(i); ranges[i] = GetLL(i); maxPref[i] = GetLL(i); maxSuf[i] = GetLL(i); maxPrefSuf[i] = GetLL(i); } vector<long long> T3(nodes+1, 0), sumBeg(nodes+1, 0); FOR(i, 0, nodes-1) { T3[i+1] = max(T3[i], sumBeg[i]+maxPref[i]); sumBeg[i+1] = sumBeg[i] + ranges[i]; #ifdef _HOMEDEBUG cout << i << "-3 " << T3[i+1] << " " << sumBeg[i+1] << endl; #endif } vector<long long> T4(nodes+1, 0), sumEnd(nodes+1, 0); FORD(i, nodes-1, 0) { T4[i] = max(T4[i+1], sumEnd[i+1]+maxSuf[i]); sumEnd[i] = sumEnd[i+1] + ranges[i]; #ifdef _HOMEDEBUG cout << i << "-4 " << T4[i] << " " << sumEnd[i] << endl; #endif } #ifdef _HOMEDEBUG cout << "T3\tT4\tPrefSuf" << endl; REP(x, nodes+1) cout << T3[x] << "\t" << T4[x] << "\t" << maxPrefSuf[x] << endl; #endif long long totalMax = 0; #ifdef _HOMEDEBUG cout << "totalMax" << endl; #endif REP(i, nodes) { long long m1 = T3[i]+T4[i], m2 = sumBeg[i]+sumEnd[i+1]+maxPrefSuf[i]; totalMax = max(totalMax, max(m1, m2)); #ifdef _HOMEDEBUG cout << m1 << " " << m2 << " -> " << totalMax << endl; #endif } cout << totalMax; } int main() { #if defined(_HOMEDEBUG) || defined(_HOMEDEBUG1) GetN(); int instances = 100; REP(x, instances) { WORKING_THREAD(x); doWork(GetN(), instances, x); } WORKING_THREAD(0); generateOutput(instances); #else int nodes = NumberOfNodes(); int myId = MyNodeId(); doWork(GetN(), nodes, myId); if(myId == 0) generateOutput(nodes); #endif return 0; } |