#include <bits/stdc++.h> using namespace std; #define PII pair<int, int> #define VI vector<int> #define VPII vector<PII> #define LL long long #define VLL vector<LL> #define LD long double #define f first #define s second #define MP make_pair #define PB push_back #define endl '\n' #define ALL(c) (c).begin(), (c).end() #define SIZ(c) (int)(c).size() #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, b, e) for (int i = (b); i <= (int)(e); i++) #define FORD(i, b, e) for (int i = (b); i >= (int)(e); i--) #define ll long long #define st f #define nd s #define pb PB #define eb emplace_back #define mp make_pair const int inf = 1e9 + 7; const LL INF = 1e18L + 7; #define sim template<class n sim, class s> ostream & operator << (ostream &p, pair<n, s> x) {return p << "<" << x.f << ", " << x.s << ">";} sim> auto operator << (ostream &p, n y) -> typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type {int o = 0; p << "{"; for (auto c : y) {if (o++) p << ", "; p << c;} return p << "}";} void dor() {cerr << endl;} sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);} sim, class s> void mini(n &p, s y) {if (p > y) p = y;} sim, class s> void maxi(n &p, s y) {if (p < y) p = y;} #ifdef DEB #define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__) #else #define debug(...) #endif #define I(x) #x " = ", (x), " " #define A(a, i) #a "[" #i " = ", i, "] = ", a[i], " " #include "kanapka.h" #include "message.h" #define int ll int n, nodes, id, len; int sufit(int a, int b) { return (a+b-1)/b; } int merge() { VLL Sum(nodes); VLL Pref(nodes); VLL Suf(nodes); VLL Seg(nodes); for(int i = 0; i < nodes; ++i) { Receive(i); Sum[i] = GetLL(i); Pref[i] = GetLL(i); Suf[i] = GetLL(i); Seg[i] = GetLL(i); } int sum = 0; int ans = 0; int curr_seg = 0; for(int i = 0; i < nodes; ++i) { sum += Sum[i]; ans = min(ans, Seg[i]); ans = min(ans, curr_seg + Pref[i]); curr_seg = min(curr_seg + Sum[i], Suf[i]); } return sum-ans; } int32_t main() { nodes = NumberOfNodes(); id = MyNodeId(); n = GetN(); len = sufit(n, nodes); int sum = 0; int min_pref = 0; int min_suf = 0; int min_seg = 0; int l = id*len; int r = min(n-1, (id+1)*len-1); int curr_pref = 0; int curr_seg = 0; for(int i = l; i <= r; ++i) { int taste = GetTaste(i); sum += taste; curr_pref += taste; curr_seg = min(taste, curr_seg+taste); min_pref = min(min_pref, curr_pref); min_seg = min(min_seg, curr_seg); } int curr_suf = 0; for(int i = r; i >= l; --i) { int taste = GetTaste(i); curr_suf += taste; min_suf = min(min_suf, curr_suf); } PutLL(0, sum); PutLL(0, min_pref); PutLL(0, min_suf); PutLL(0, min_seg); Send(0); if(id==0) cout << merge() << endl; }
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 | #include <bits/stdc++.h> using namespace std; #define PII pair<int, int> #define VI vector<int> #define VPII vector<PII> #define LL long long #define VLL vector<LL> #define LD long double #define f first #define s second #define MP make_pair #define PB push_back #define endl '\n' #define ALL(c) (c).begin(), (c).end() #define SIZ(c) (int)(c).size() #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, b, e) for (int i = (b); i <= (int)(e); i++) #define FORD(i, b, e) for (int i = (b); i >= (int)(e); i--) #define ll long long #define st f #define nd s #define pb PB #define eb emplace_back #define mp make_pair const int inf = 1e9 + 7; const LL INF = 1e18L + 7; #define sim template<class n sim, class s> ostream & operator << (ostream &p, pair<n, s> x) {return p << "<" << x.f << ", " << x.s << ">";} sim> auto operator << (ostream &p, n y) -> typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type {int o = 0; p << "{"; for (auto c : y) {if (o++) p << ", "; p << c;} return p << "}";} void dor() {cerr << endl;} sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);} sim, class s> void mini(n &p, s y) {if (p > y) p = y;} sim, class s> void maxi(n &p, s y) {if (p < y) p = y;} #ifdef DEB #define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__) #else #define debug(...) #endif #define I(x) #x " = ", (x), " " #define A(a, i) #a "[" #i " = ", i, "] = ", a[i], " " #include "kanapka.h" #include "message.h" #define int ll int n, nodes, id, len; int sufit(int a, int b) { return (a+b-1)/b; } int merge() { VLL Sum(nodes); VLL Pref(nodes); VLL Suf(nodes); VLL Seg(nodes); for(int i = 0; i < nodes; ++i) { Receive(i); Sum[i] = GetLL(i); Pref[i] = GetLL(i); Suf[i] = GetLL(i); Seg[i] = GetLL(i); } int sum = 0; int ans = 0; int curr_seg = 0; for(int i = 0; i < nodes; ++i) { sum += Sum[i]; ans = min(ans, Seg[i]); ans = min(ans, curr_seg + Pref[i]); curr_seg = min(curr_seg + Sum[i], Suf[i]); } return sum-ans; } int32_t main() { nodes = NumberOfNodes(); id = MyNodeId(); n = GetN(); len = sufit(n, nodes); int sum = 0; int min_pref = 0; int min_suf = 0; int min_seg = 0; int l = id*len; int r = min(n-1, (id+1)*len-1); int curr_pref = 0; int curr_seg = 0; for(int i = l; i <= r; ++i) { int taste = GetTaste(i); sum += taste; curr_pref += taste; curr_seg = min(taste, curr_seg+taste); min_pref = min(min_pref, curr_pref); min_seg = min(min_seg, curr_seg); } int curr_suf = 0; for(int i = r; i >= l; --i) { int taste = GetTaste(i); curr_suf += taste; min_suf = min(min_suf, curr_suf); } PutLL(0, sum); PutLL(0, min_pref); PutLL(0, min_suf); PutLL(0, min_seg); Send(0); if(id==0) cout << merge() << endl; } |