#include<bits/stdc++.h> #include"kanapka.h" #include"message.h" #define VAR(i,n) __typeof(n) i = (n) #define loop(i,j,s) for(int i=j;i<s;i++) #define loopback(i,j,s) for(int i=j;i>=s;i--) #define foreach(i,c) for(VAR(i,(c).begin());i!=(c).end();i++) #define pln( x ) cout << x << "\n" #define ps( x ) cout << x << " " #define entr cout << "\n" #define pcnt(i) __builtin_popcount(i) #define ll long long #define pb push_back #define mp make_pair #define ff first #define ss second #define SIZE(c) (c).size() #define ALL(c) (c).begin(), (c).end() using namespace std; typedef vector<int> VI; const int INFTY=20000000; const int MAX=5000100; const int MOD=10000000; void coutTab(int* tab,int n){ loop(i,0,n){ cout<<tab[i]<<" "; } cout<<"\n"; } //------------------------------------------ ll bestS[MAX],bestSrev[MAX]; ll sums[11],pref[11],bestSt[11],bestEn[11],bestMid[11]; int main(){ ios_base::sync_with_stdio(0); ll S=0; ll Ss=0; ll Se=0; ll bs,be; ll N=GetN(); int s=MyNodeId()*N/NumberOfNodes(); int e=(MyNodeId()+1)*N/NumberOfNodes(); ll bSs=0,bSe=0; if(MyNodeId()!=0){ loop(i,s,e){ if(i!=s) bestS[i-s]=max(bestS[i-s],S); ll t=GetTaste(i); S+=t; bSe=max(bSs,S); } } if(MyNodeId()!=NumberOfNodes()-1){ S=0; loopback(i,e-1,s){ if(i!=e-1) bestSrev[i-s]=max(bestSrev[i-s+1],S); ll t=GetTaste(i); S+=t; bSe=max(bSe,S); } } ll bS=S; loop(i,s,e){ bS=max(bestS[i-s]+bestSrev[i-s],bS); } if(MyNodeId()>0){ PutLL(0,S); PutLL(0,bS); PutLL(0,bSs); PutLL(0,bSe); Send(0); }else{ sums[0]=S; loop(i,1,NumberOfNodes()){ int inst=Receive(-1); sums[inst]=GetLL(inst); bestMid[inst]=GetLL(inst); bestSt[inst]=GetLL(inst); bestEn[inst]=GetLL(inst); //ps(inst);ps(sums[inst]);ps(bestSt[inst]);ps(bestEn[inst]);pln(bestMid[inst]); } bestSt[0]=bSs; bestEn[0]=bSe; bestS[0]=bestSt[0]; S=sums[0]; loop(i,1,NumberOfNodes()){ bestS[i]=max(bestS[i-1],S+bestSt[i-1]); S+=sums[i]; } S=sums[NumberOfNodes()-1]; bestSrev[NumberOfNodes()-1]=bestEn[NumberOfNodes()-1]; loop(i,NumberOfNodes()-2,0){ bestSrev[i]=max(bestSrev[i+1],S+bestEn[i+1]); S+=sums[i]; } pref[0]=sums[0]; loop(i,1,NumberOfNodes()) pref[i]=pref[i-1]+sums[i]; S=0; bS=0; loopback(i,NumberOfNodes()-1,0){ if(i!=0) bS=max(pref[i-1]+bestMid[i]+S,bS); else bS=max(bestMid[i]+S,bS); if(i!=0) bS=max(bS,bestS[i-1]+bestSrev[i]); else bS=max(bS,bestSrev[i]); S+=sums[i]; } bs=max(bs,bestSrev[NumberOfNodes()-1]); pln(bS); } }
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 | #include<bits/stdc++.h> #include"kanapka.h" #include"message.h" #define VAR(i,n) __typeof(n) i = (n) #define loop(i,j,s) for(int i=j;i<s;i++) #define loopback(i,j,s) for(int i=j;i>=s;i--) #define foreach(i,c) for(VAR(i,(c).begin());i!=(c).end();i++) #define pln( x ) cout << x << "\n" #define ps( x ) cout << x << " " #define entr cout << "\n" #define pcnt(i) __builtin_popcount(i) #define ll long long #define pb push_back #define mp make_pair #define ff first #define ss second #define SIZE(c) (c).size() #define ALL(c) (c).begin(), (c).end() using namespace std; typedef vector<int> VI; const int INFTY=20000000; const int MAX=5000100; const int MOD=10000000; void coutTab(int* tab,int n){ loop(i,0,n){ cout<<tab[i]<<" "; } cout<<"\n"; } //------------------------------------------ ll bestS[MAX],bestSrev[MAX]; ll sums[11],pref[11],bestSt[11],bestEn[11],bestMid[11]; int main(){ ios_base::sync_with_stdio(0); ll S=0; ll Ss=0; ll Se=0; ll bs,be; ll N=GetN(); int s=MyNodeId()*N/NumberOfNodes(); int e=(MyNodeId()+1)*N/NumberOfNodes(); ll bSs=0,bSe=0; if(MyNodeId()!=0){ loop(i,s,e){ if(i!=s) bestS[i-s]=max(bestS[i-s],S); ll t=GetTaste(i); S+=t; bSe=max(bSs,S); } } if(MyNodeId()!=NumberOfNodes()-1){ S=0; loopback(i,e-1,s){ if(i!=e-1) bestSrev[i-s]=max(bestSrev[i-s+1],S); ll t=GetTaste(i); S+=t; bSe=max(bSe,S); } } ll bS=S; loop(i,s,e){ bS=max(bestS[i-s]+bestSrev[i-s],bS); } if(MyNodeId()>0){ PutLL(0,S); PutLL(0,bS); PutLL(0,bSs); PutLL(0,bSe); Send(0); }else{ sums[0]=S; loop(i,1,NumberOfNodes()){ int inst=Receive(-1); sums[inst]=GetLL(inst); bestMid[inst]=GetLL(inst); bestSt[inst]=GetLL(inst); bestEn[inst]=GetLL(inst); //ps(inst);ps(sums[inst]);ps(bestSt[inst]);ps(bestEn[inst]);pln(bestMid[inst]); } bestSt[0]=bSs; bestEn[0]=bSe; bestS[0]=bestSt[0]; S=sums[0]; loop(i,1,NumberOfNodes()){ bestS[i]=max(bestS[i-1],S+bestSt[i-1]); S+=sums[i]; } S=sums[NumberOfNodes()-1]; bestSrev[NumberOfNodes()-1]=bestEn[NumberOfNodes()-1]; loop(i,NumberOfNodes()-2,0){ bestSrev[i]=max(bestSrev[i+1],S+bestEn[i+1]); S+=sums[i]; } pref[0]=sums[0]; loop(i,1,NumberOfNodes()) pref[i]=pref[i-1]+sums[i]; S=0; bS=0; loopback(i,NumberOfNodes()-1,0){ if(i!=0) bS=max(pref[i-1]+bestMid[i]+S,bS); else bS=max(bestMid[i]+S,bS); if(i!=0) bS=max(bS,bestS[i-1]+bestSrev[i]); else bS=max(bS,bestSrev[i]); S+=sums[i]; } bs=max(bs,bestSrev[NumberOfNodes()-1]); pln(bS); } } |