#include <iostream> #include "kanapka.h" #include "message.h" using namespace std; long long tab[5000002], pref[5000002], suf[5000002]; /*int n; void init() { cin >> n; for (int i=0; i<n; i++) cin >> tab[i]; } int MyNodeId() { return 0; } long long GetN() { return n; } long long GetTaste(int i) { return tab[i]; } int GetLL(int a) { return 0; } void Send(int who) { return; } int Receive(int who) { return -1; } void PutLL(int a, int b) { return; }*/ int main() { //init(); int kto=MyNodeId(); int pocz=kto*(1e6)*5, kon=pocz+(1e6)*5-1; kon=min(kon, (int)GetN()-1); if (kon<pocz) return 0; long long sum=0, localmaks=0; for (int i=pocz; i<=kon; i++) { tab[i-pocz]=GetTaste(i); sum+=tab[i-pocz]; if (i==pocz) pref[i-pocz]=tab[i-pocz]; else pref[i-pocz]=tab[i-pocz]+pref[i-pocz-1]; localmaks=max(localmaks, pref[i-pocz]); } for (int i=kon; i>=pocz; i--) { if (i==kon) suf[i-pocz]=tab[i-pocz]; else suf[i-pocz]=tab[i-pocz]+suf[i+1-pocz]; } int blah=0; long long popsum=0, maks=0, nextsum=0, wyn=0; if (kto!=0) { blah=Receive(kto-1); popsum=GetLL(kto-1); maks=GetLL(kto-1); } if (GetN()-1!=kon) { PutLL(kto+1, popsum+sum); PutLL(kto+1, max(localmaks+popsum, maks)); Send(kto+1); blah=Receive(kto+1); nextsum=GetLL(kto+1); } if (kto!=0) { PutLL(kto-1, nextsum+sum); Send(kto-1); } for (int i=0; i<=kon-pocz; i++) { pref[i]+=popsum; suf[i]+=nextsum; wyn=max(wyn, maks+suf[i]); maks=max(maks, pref[i]); //cout << wyn << " " << maks << " " << suf[i] << i << "\n"; } wyn=max(wyn, maks); if (GetN()-1!=kon) { blah=Receive(kto+1); long long pomwyn=GetLL(kto+1); wyn=max(wyn, pomwyn); } if (kto!=0) { PutLL(kto-1, wyn); Send(kto-1); } else { cout << wyn; } } /* 7 1 -3 4 2 -1 3 -5 */
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 | #include <iostream> #include "kanapka.h" #include "message.h" using namespace std; long long tab[5000002], pref[5000002], suf[5000002]; /*int n; void init() { cin >> n; for (int i=0; i<n; i++) cin >> tab[i]; } int MyNodeId() { return 0; } long long GetN() { return n; } long long GetTaste(int i) { return tab[i]; } int GetLL(int a) { return 0; } void Send(int who) { return; } int Receive(int who) { return -1; } void PutLL(int a, int b) { return; }*/ int main() { //init(); int kto=MyNodeId(); int pocz=kto*(1e6)*5, kon=pocz+(1e6)*5-1; kon=min(kon, (int)GetN()-1); if (kon<pocz) return 0; long long sum=0, localmaks=0; for (int i=pocz; i<=kon; i++) { tab[i-pocz]=GetTaste(i); sum+=tab[i-pocz]; if (i==pocz) pref[i-pocz]=tab[i-pocz]; else pref[i-pocz]=tab[i-pocz]+pref[i-pocz-1]; localmaks=max(localmaks, pref[i-pocz]); } for (int i=kon; i>=pocz; i--) { if (i==kon) suf[i-pocz]=tab[i-pocz]; else suf[i-pocz]=tab[i-pocz]+suf[i+1-pocz]; } int blah=0; long long popsum=0, maks=0, nextsum=0, wyn=0; if (kto!=0) { blah=Receive(kto-1); popsum=GetLL(kto-1); maks=GetLL(kto-1); } if (GetN()-1!=kon) { PutLL(kto+1, popsum+sum); PutLL(kto+1, max(localmaks+popsum, maks)); Send(kto+1); blah=Receive(kto+1); nextsum=GetLL(kto+1); } if (kto!=0) { PutLL(kto-1, nextsum+sum); Send(kto-1); } for (int i=0; i<=kon-pocz; i++) { pref[i]+=popsum; suf[i]+=nextsum; wyn=max(wyn, maks+suf[i]); maks=max(maks, pref[i]); //cout << wyn << " " << maks << " " << suf[i] << i << "\n"; } wyn=max(wyn, maks); if (GetN()-1!=kon) { blah=Receive(kto+1); long long pomwyn=GetLL(kto+1); wyn=max(wyn, pomwyn); } if (kto!=0) { PutLL(kto-1, wyn); Send(kto-1); } else { cout << wyn; } } /* 7 1 -3 4 2 -1 3 -5 */ |