CF799C Fountains
\n\u53ef\u4ee5\u4e0a\u6570\u636e\u7ed3\u6784\u7ef4\u62a4\uff0c\u5f53\u7136\u4e5f\u53ef\u4ee5\u5927\u529b\u5206\u7c7b\u8ba8\u8bba\u3002 <\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<algorithm>\r\nusing namespace std;\r\nint n,A,B,Ct=0,Dt=0;\r\nstruct data{\r\n int b;\r\n int p;\r\n bool operator <(const data &_B)const{\r\n return p<_B.p;\r\n }\r\n}C[100005],D[100005];\r\ninline int slv1(){\r\n if((!Ct)||(!Dt)){\r\n return 0;\r\n }\r\n if(C[1].p>A||D[1].p>B){\r\n return 0;\r\n }\r\n int rtC=0,rtD=0,pC=1,pD=1;\r\n while(pC<=Ct&&C[pC].p<=A){\r\n rtC=max(rtC,C[pC].b);\r\n ++pC;\r\n }\r\n while(pD<=Dt&&D[pD].p<=B){\r\n rtD=max(rtD,D[pD].b);\r\n ++pD;\r\n }\r\n return rtC+rtD;\r\n}\r\n\/\/AC[i]\u8868\u793a\uff0c\u5269\u4f59\u4e3ai\u65f6\u7684\u6700\u5927\u6536\u76ca\uff0crAC[i]\u8868\u793a\uff0c\u5269\u4f59\u5927\u4e8e\u7b49\u4e8ei\u65f6\u7684\u6700\u5927\u6536\u76ca\u3002 sAC\u4e0esrAC\u5206\u522b\u8868\u793a\u5b83\u4eec\u7684\u4f4d\u7f6e\u3002 \r\nint AC[100005],rAC[100005],sAC[100005],srAC[100005],sbAC[100005];\r\ninline int slv2(){\r\n if(Ct<2){\r\n return 0;\r\n }\r\n if(C[1].p+C[2].p>A){\r\n return 0;\r\n }\r\n int rtC=0;\r\n for(int i=1;i<=Ct&&C[i].p<=A;++i){\r\n if(AC[A-C[i].p]<C[i].b){\r\n AC[A-C[i].p]=C[i].b,sAC[A-C[i].p]=i;\r\n }\r\n }\r\n for(int i=A;i>=1;--i){\r\n if(rAC[i+1]>AC[i]){\r\n rAC[i]=rAC[i+1];\r\n srAC[i]=srAC[i+1]; \r\n }else{\r\n rAC[i]=AC[i];\r\n srAC[i]=sAC[i]; \r\n }\r\n }\r\n for(int i=1;i<=Ct;++i){\r\n if(i!=srAC[C[i].p]&&rAC[C[i].p]){\r\n rtC=max(rtC,C[i].b+rAC[C[i].p]);\r\n }else{\r\n \t\/\/rtC=max(rtC,C[i].b+C[i-1].b);\r\n\t\t}\r\n }\r\n return rtC;\r\n}\r\n\r\nint BD[100005],rBD[100005],sBD[100005],srBD[100005];\r\ninline int slv3(){\r\n if(Dt<2){\r\n return 0;\r\n }\r\n if(D[1].p+D[2].p>B){\r\n return 0;\r\n }\r\n int rtD=0;\r\n for(int i=1;i<=Dt&&D[i].p<=B;++i){\r\n if(BD[B-D[i].p]<D[i].b){\r\n BD[B-D[i].p]=D[i].b,sBD[B-D[i].p]=i;\r\n }\r\n }\r\n for(int i=B;i>=1;--i){\r\n if(rBD[i+1]>BD[i]){\r\n rBD[i]=rBD[i+1];\r\n srBD[i]=srBD[i+1]; \r\n }else{\r\n rBD[i]=BD[i];\r\n srBD[i]=sBD[i]; \r\n }\r\n }\r\n for(int i=1;i<=Dt;++i){\r\n if(i!=srBD[D[i].p]&&rBD[D[i].p]){\r\n rtD=max(rtD,D[i].b+rBD[D[i].p]);\r\n }\r\n }\r\n return rtD;\r\n}\r\nvoid init(){\r\n scanf(\"%d%d%d\",&n,&A,&B);\r\n char ch[5];\r\n int x,y;\r\n for(int i=1;i<=n;++i){\r\n scanf(\"%d%d\",&x,&y);\r\n cin>>ch;\r\n if(ch[0]=='C'){\r\n C[++Ct]=(data){x,y};\r\n }else{\r\n D[++Dt]=(data){x,y};\r\n }\r\n }\r\n sort(C+1,C+1+Ct);\r\n sort(D+1,D+1+Dt);\r\n int ans=0;\r\n ans=max(ans,slv1());\r\n ans=max(ans,slv2());\r\n ans=max(ans,slv3());\r\n printf(\"%d\\n\",ans);\r\n}\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
CF799C Fountains \u53ef\u4ee5\u4e0a\u6570\u636e\u7ed3\u6784\u7ef4\u62a4\uff0c\u5f53\u7136\u4e5f\u53ef\u4ee5\u5927\u529b\u5206\u7c7b\u8ba8\u8bba\u3002 #include<ios … <\/p>\n