// Artur Kraska, II UWr #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; long long n, a; long long N, numer; struct str { long long min_l, min_p; long long suma, minn; }; str e, e2, e3; int main() { N = NumberOfNodes(); n = GetN(); numer = MyNodeId(); long long pocz = numer*n/N; long long kon = (numer+1)*n/N; FOR(i, pocz, kon-1) { a = GetTaste(i); e.suma += a; e.min_l = min(e.min_l, e.suma); e.min_p = min(e.min_p+a, min(a, 0ll)); e.minn = min(e.minn, e.min_p); //cout << a << " -> l: " << e.min_l << ", p: " << e.min_p << ", suma: " << e.suma << ", min: " << e.minn << endl; } if(numer != 0) { PutLL(0, e.suma); PutLL(0, e.minn); PutLL(0, e.min_l); PutLL(0, e.min_p); Send(0); } else { FOR(i, 1, N-1) { Receive(i); e2.suma = GetLL(i); e2.minn = GetLL(i); e2.min_l = GetLL(i); e2.min_p = GetLL(i); e3.suma = e.suma + e2.suma; e3.min_l = min(e.min_l, e.suma + e2.min_l); e3.min_p = min(e2.min_p, e2.suma + e.min_p); e3.minn = min(min(e.minn, e2.minn), e.min_p + e2.min_l); e = e3; } cout << e.suma - e.minn << endl; } 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 | // Artur Kraska, II UWr #include "kanapka.h" #include "message.h" #include <algorithm> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <vector> #include <cmath> #include <list> #include <set> #include <map> #define forr(i, n) for(int i=0; i<n; i++) #define FOREACH(iter, coll) for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter) #define FOREACHR(iter, coll) for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter) #define lbound(P,R,PRED) ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;}) #define testy() int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests) #define CLEAR(tab) memset(tab, 0, sizeof(tab)) #define CONTAIN(el, coll) (coll.find(el) != coll.end()) #define FOR(i, a, b) for(int i=a; i<=b; i++) #define FORD(i, a, b) for(int i=a; i>=b; i--) #define MP make_pair #define PB push_back #define deb(X) X; #define M 1000000007 #define INF 1000000007 using namespace std; long long n, a; long long N, numer; struct str { long long min_l, min_p; long long suma, minn; }; str e, e2, e3; int main() { N = NumberOfNodes(); n = GetN(); numer = MyNodeId(); long long pocz = numer*n/N; long long kon = (numer+1)*n/N; FOR(i, pocz, kon-1) { a = GetTaste(i); e.suma += a; e.min_l = min(e.min_l, e.suma); e.min_p = min(e.min_p+a, min(a, 0ll)); e.minn = min(e.minn, e.min_p); //cout << a << " -> l: " << e.min_l << ", p: " << e.min_p << ", suma: " << e.suma << ", min: " << e.minn << endl; } if(numer != 0) { PutLL(0, e.suma); PutLL(0, e.minn); PutLL(0, e.min_l); PutLL(0, e.min_p); Send(0); } else { FOR(i, 1, N-1) { Receive(i); e2.suma = GetLL(i); e2.minn = GetLL(i); e2.min_l = GetLL(i); e2.min_p = GetLL(i); e3.suma = e.suma + e2.suma; e3.min_l = min(e.min_l, e.suma + e2.min_l); e3.min_p = min(e2.min_p, e2.suma + e.min_p); e3.minn = min(min(e.minn, e2.minn), e.min_p + e2.min_l); e = e3; } cout << e.suma - e.minn << endl; } return 0; } |