fork download 
  1. #include<bits/stdc++.h>
  2. #pragma GCC optimize("Ofast")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. using namespace std;
  5. #define int long long
  6. #define all(x) x.begin(),x.end()
  7. #define pb push_back
  8. #define rall(x) x.rbegin(),x.rend()
  9. const int N=1e5+2,mod=998244353,MOD=1e9+7,INF=9223372036854775806;
  10. int a[N],b[N],c[N];
  11. void build(int t[],int a[],int v,int tl,int tr){
  12.     if(tl==tr){
  13.         t[v]=a[tl];
  14.         return;
  15.     }
  16.     int m=(tl+tr)/2;
  17.     build(t,a,v+v,tl,m);
  18.     build(t,a,v+v+1,m+1,tr);
  19.     t[v]=max(t[v+v],t[v+v+1]);
  20. }
  21. int get(int t[],int v,int tl,int tr,int l,int r){
  22.     if(l>tr||r<tl){
  23.         return -INF;
  24.     }
  25.     else if(tl>=l&&tr<=r){
  26.         return t[v];
  27.     }
  28.     int m=(tl+tr)/2;
  29.     return max(get(t,v+v,tl,m,l,r),get(t,v+v+1,m+1,tr,l,r));
  30. }
  31. signed main(){
  32.     ios::sync_with_stdio(false);
  33.     cin.tie(NULL);
  34.     //freopen("input.txt","r",stdin);
  35.     //freopen("output.txt","w",stdout);
  36.     int T=1;
  37.     cin>>T;
  38.     while(T--){
  39.         int n,ans=0;
  40.         cin>>n;
  41.         int p2[n+2],s2[n+2],p3[n+2],s3[n+2],t2[n+n+n+n+2],t3[n+n+n+n+2];
  42.         p2[0]=0;
  43.         s2[n+1]=0;
  44.         p3[0]=0;
  45.         s3[n+1]=0;
  46.         map<int,vector<int>>pos2,pos3;
  47.         for(int i=1;i<=n;i++){
  48.             cin>>a[i];
  49.         }
  50.         for(int i=1;i<=n;i++){
  51.             cin>>b[i];
  52.             pos2[b[i]].pb(i);
  53.         }
  54.         for(int i=1;i<=n;i++){
  55.             cin>>c[i];
  56.             pos3[c[i]].pb(i);
  57.         }
  58.         build(t2,b,1,1,n);
  59.         build(t3,c,1,1,n);
  60.         for(int i=1;i<=n;i++){
  61.             p2[i]=max(p2[i-1],b[i]);
  62.             p3[i]=max(p3[i-1],c[i]);
  63.         }
  64.         for(int i=n;i>=1;i--){
  65.             s2[i]=max(s2[i+1],b[i]);
  66.             s3[i]=max(s3[i+1],c[i]);
  67.         }
  68.         for(int i=1;i<=n;i++){
  69.             int x=max(p2[i-1],s2[i+1]),y=max(p3[i-1],s3[i+1]);
  70.             if(pos2[x].size()>2||pos3[y].size()>2){
  71.                 ans=max(ans,a[i]+x+y);
  72.             }
  73.             else if(pos2[x].size()==1&&pos3[y].size()==1){
  74.                 if(pos2[x][0]==pos3[y][0]){
  75.                     int x1=x,y1=0,x2=0,y2=y,j1=pos2[x][0],j2=pos3[y][0];
  76.                     if(j1<i){
  77.                         if(1<=j1-1){
  78.                             y1=max(y1,get(t3,1,1,n,1,j1-1));
  79.                         }
  80.                         if(j1+1<=i-1){
  81.                             y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  82.                         }
  83.                         if(i+1<=n){
  84.                             y1=max(y1,get(t3,1,1,n,i+1,n));
  85.                         }
  86.                     }
  87.                     else if(i<j1){
  88.                         if(1<=i-1){
  89.                             y1=max(y1,get(t3,1,1,n,1,i-1));
  90.                         }
  91.                         if(i+1<=j1-1){
  92.                             y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  93.                         }
  94.                         if(j1+1<=n){
  95.                             y1=max(y1,get(t3,1,1,n,j1+1,n));
  96.                         }
  97.                     }
  98.                     if(j2<i){
  99.                         if(1<=j2-1){
  100.                             x2=max(x2,get(t2,1,1,n,1,j2-1));
  101.                         }
  102.                         if(j2+1<=i-1){
  103.                             x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  104.                         }
  105.                         if(i+1<=n){
  106.                             x2=max(x2,get(t2,1,1,n,i+1,n));
  107.                         }
  108.                     }
  109.                     else if(i<j2){
  110.                         if(1<=i-1){
  111.                             x2=max(x2,get(t2,1,1,n,1,i-1));
  112.                         }
  113.                         if(i+1<=j2-1){
  114.                             x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  115.                         }
  116.                         if(j2+1<=n){
  117.                             x2=max(x2,get(t2,1,1,n,j2+1,n));
  118.                         }
  119.                     }
  120.                     ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  121.                 }
  122.                 else{
  123.                     ans=max(ans,a[i]+x+y);
  124.                 }
  125.             }
  126.             else if(pos2[x].size()==2&&pos3[y].size()==1){
  127.                 if(pos2[x][0]!=i&&pos2[x][1]!=i){
  128.                     ans=max(ans,a[i]+x+y);
  129.                 }
  130.                 else{
  131.                     if(pos2[x][0]!=i&&pos2[x][0]==pos3[y][0]){
  132.                         int x1=x,y1=0,x2=0,y2=y,j1=pos2[x][0],j2=pos3[y][0];
  133.                         if(j1<i){
  134.                             if(1<=j1-1){
  135.                                 y1=max(y1,get(t3,1,1,n,1,j1-1));
  136.                             }
  137.                             if(j1+1<=i-1){
  138.                                 y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  139.                             }
  140.                             if(i+1<=n){
  141.                                 y1=max(y1,get(t3,1,1,n,i+1,n));
  142.                             }
  143.                         }
  144.                         else if(i<j1){
  145.                             if(1<=i-1){
  146.                                 y1=max(y1,get(t3,1,1,n,1,i-1));
  147.                             }
  148.                             if(i+1<=j1-1){
  149.                                 y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  150.                             }
  151.                             if(j1+1<=n){
  152.                                 y1=max(y1,get(t3,1,1,n,j1+1,n));
  153.                             }
  154.                         }
  155.                         if(j2<i){
  156.                             if(1<=j2-1){
  157.                                 x2=max(x2,get(t2,1,1,n,1,j2-1));
  158.                             }
  159.                             if(j2+1<=i-1){
  160.                                 x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  161.                             }
  162.                             if(i+1<=n){
  163.                                 x2=max(x2,get(t2,1,1,n,i+1,n));
  164.                             }
  165.                         }
  166.                         else if(i<j2){
  167.                             if(1<=i-1){
  168.                                 x2=max(x2,get(t2,1,1,n,1,i-1));
  169.                             }
  170.                             if(i+1<=j2-1){
  171.                                 x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  172.                             }
  173.                             if(j2+1<=n){
  174.                                 x2=max(x2,get(t2,1,1,n,j2+1,n));
  175.                             }
  176.                         }
  177.                         ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  178.                     }
  179.                     else if(pos2[x][0]==i&&pos2[x][1]==pos3[y][0]){
  180.                         int x1=x,y1=0,x2=0,y2=y,j1=pos2[x][1],j2=pos3[y][0];
  181.                         if(j1<i){
  182.                             if(1<=j1-1){
  183.                                 y1=max(y1,get(t3,1,1,n,1,j1-1));
  184.                             }
  185.                             if(j1+1<=i-1){
  186.                                 y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  187.                             }
  188.                             if(i+1<=n){
  189.                                 y1=max(y1,get(t3,1,1,n,i+1,n));
  190.                             }
  191.                         }
  192.                         else if(i<j1){
  193.                             if(1<=i-1){
  194.                                 y1=max(y1,get(t3,1,1,n,1,i-1));
  195.                             }
  196.                             if(i+1<=j1-1){
  197.                                 y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  198.                             }
  199.                             if(j1+1<=n){
  200.                                 y1=max(y1,get(t3,1,1,n,j1+1,n));
  201.                             }
  202.                         }
  203.                         if(j2<i){
  204.                             if(1<=j2-1){
  205.                                 x2=max(x2,get(t2,1,1,n,1,j2-1));
  206.                             }
  207.                             if(j2+1<=i-1){
  208.                                 x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  209.                             }
  210.                             if(i+1<=n){
  211.                                 x2=max(x2,get(t2,1,1,n,i+1,n));
  212.                             }
  213.                         }
  214.                         else if(i<j2){
  215.                             if(1<=i-1){
  216.                                 x2=max(x2,get(t2,1,1,n,1,i-1));
  217.                             }
  218.                             if(i+1<=j2-1){
  219.                                 x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  220.                             }
  221.                             if(j2+1<=n){
  222.                                 x2=max(x2,get(t2,1,1,n,j2+1,n));
  223.                             }
  224.                         }
  225.                         ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  226.                     }
  227.                     else{
  228.                         ans=max(ans,a[i]+x+y);
  229.                     }
  230.                 }
  231.             }
  232.             else if(pos2[x].size()==1&&pos3[y].size()==2){
  233.                 if(pos3[y][0]!=i&&pos3[y][1]!=i){
  234.                     ans=max(ans,a[i]+x+y);
  235.                 }
  236.                 else{
  237.                     if(pos3[y][0]!=i&&pos2[x][0]==pos3[y][0]){
  238.                         int x1=x,y1=0,x2=0,y2=y,j1=pos2[x][0],j2=pos3[y][0];
  239.                         if(j1<i){
  240.                             if(1<=j1-1){
  241.                                 y1=max(y1,get(t3,1,1,n,1,j1-1));
  242.                             }
  243.                             if(j1+1<=i-1){
  244.                                 y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  245.                             }
  246.                             if(i+1<=n){
  247.                                 y1=max(y1,get(t3,1,1,n,i+1,n));
  248.                             }
  249.                         }
  250.                         else if(i<j1){
  251.                             if(1<=i-1){
  252.                                 y1=max(y1,get(t3,1,1,n,1,i-1));
  253.                             }
  254.                             if(i+1<=j1-1){
  255.                                 y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  256.                             }
  257.                             if(j1+1<=n){
  258.                                 y1=max(y1,get(t3,1,1,n,j1+1,n));
  259.                             }
  260.                         }
  261.                         if(j2<i){
  262.                             if(1<=j2-1){
  263.                                 x2=max(x2,get(t2,1,1,n,1,j2-1));
  264.                             }
  265.                             if(j2+1<=i-1){
  266.                                 x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  267.                             }
  268.                             if(i+1<=n){
  269.                                 x2=max(x2,get(t2,1,1,n,i+1,n));
  270.                             }
  271.                         }
  272.                         else if(i<j2){
  273.                             if(1<=i-1){
  274.                                 x2=max(x2,get(t2,1,1,n,1,i-1));
  275.                             }
  276.                             if(i+1<=j2-1){
  277.                                 x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  278.                             }
  279.                             if(j2+1<=n){
  280.                                 x2=max(x2,get(t2,1,1,n,j2+1,n));
  281.                             }
  282.                         }
  283.                         ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  284.                     }
  285.                     else if(pos3[y][0]==i&&pos3[y][1]==pos2[x][0]){
  286.                         int x1=x,y1=0,x2=0,y2=y,j1=pos2[x][0],j2=pos3[y][1];
  287.                         if(j1<i){
  288.                             if(1<=j1-1){
  289.                                 y1=max(y1,get(t3,1,1,n,1,j1-1));
  290.                             }
  291.                             if(j1+1<=i-1){
  292.                                 y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  293.                             }
  294.                             if(i+1<=n){
  295.                                 y1=max(y1,get(t3,1,1,n,i+1,n));
  296.                             }
  297.                         }
  298.                         else if(i<j1){
  299.                             if(1<=i-1){
  300.                                 y1=max(y1,get(t3,1,1,n,1,i-1));
  301.                             }
  302.                             if(i+1<=j1-1){
  303.                                 y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  304.                             }
  305.                             if(j1+1<=n){
  306.                                 y1=max(y1,get(t3,1,1,n,j1+1,n));
  307.                             }
  308.                         }
  309.                         if(j2<i){
  310.                             if(1<=j2-1){
  311.                                 x2=max(x2,get(t2,1,1,n,1,j2-1));
  312.                             }
  313.                             if(j2+1<=i-1){
  314.                                 x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  315.                             }
  316.                             if(i+1<=n){
  317.                                 x2=max(x2,get(t2,1,1,n,i+1,n));
  318.                             }
  319.                         }
  320.                         else if(i<j2){
  321.                             if(1<=i-1){
  322.                                 x2=max(x2,get(t2,1,1,n,1,i-1));
  323.                             }
  324.                             if(i+1<=j2-1){
  325.                                 x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  326.                             }
  327.                             if(j2+1<=n){
  328.                                 x2=max(x2,get(t2,1,1,n,j2+1,n));
  329.                             }
  330.                         }
  331.                         ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  332.                     }
  333.                     else{
  334.                         ans=max(ans,a[i]+x+y);
  335.                     }
  336.                 }
  337.             }
  338.             else if(pos2[x].size()==2&&pos3[y].size()==2){
  339.                 vector<int>q2,q3;
  340.                 if(pos2[x][0]!=i){
  341.                     q2.pb(pos2[x][0]);
  342.                 }
  343.                 if(pos2[x][1]!=i){
  344.                     q2.pb(pos2[x][1]);
  345.                 }
  346.                 if(pos3[y][0]!=i){
  347.                     q3.pb(pos3[y][0]);
  348.                 }
  349.                 if(pos3[y][1]!=i){
  350.                     q3.pb(pos3[y][1]);
  351.                 }
  352.                 if(q2.size()>1||q3.size()>1){
  353.                     ans=max(ans,a[i]+x+y);
  354.                 }
  355.                 else{
  356.                     if(q2[0]==q3[0]){
  357.                         int x1=x,y1=0,x2=0,y2=y,j1=q2[0],j2=q3[0];
  358.                         if(j1<i){
  359.                             if(1<=j1-1){
  360.                                 y1=max(y1,get(t3,1,1,n,1,j1-1));
  361.                             }
  362.                             if(j1+1<=i-1){
  363.                                 y1=max(y1,get(t3,1,1,n,j1+1,i-1));
  364.                             }
  365.                             if(i+1<=n){
  366.                                 y1=max(y1,get(t3,1,1,n,i+1,n));
  367.                             }
  368.                         }
  369.                         else if(i<j1){
  370.                             if(1<=i-1){
  371.                                 y1=max(y1,get(t3,1,1,n,1,i-1));
  372.                             }
  373.                             if(i+1<=j1-1){
  374.                                 y1=max(y1,get(t3,1,1,n,i+1,j1-1));
  375.                             }
  376.                             if(j1+1<=n){
  377.                                 y1=max(y1,get(t3,1,1,n,j1+1,n));
  378.                             }
  379.                         }
  380.                         if(j2<i){
  381.                             if(1<=j2-1){
  382.                                 x2=max(x2,get(t2,1,1,n,1,j2-1));
  383.                             }
  384.                             if(j2+1<=i-1){
  385.                                 x2=max(x2,get(t2,1,1,n,j2+1,i-1));
  386.                             }
  387.                             if(i+1<=n){
  388.                                 x2=max(x2,get(t2,1,1,n,i+1,n));
  389.                             }
  390.                         }
  391.                         else if(i<j2){
  392.                             if(1<=i-1){
  393.                                 x2=max(x2,get(t2,1,1,n,1,i-1));
  394.                             }
  395.                             if(i+1<=j2-1){
  396.                                 x2=max(x2,get(t2,1,1,n,i+1,j2-1));
  397.                             }
  398.                             if(j2+1<=n){
  399.                                 x2=max(x2,get(t2,1,1,n,j2+1,n));
  400.                             }
  401.                         }
  402.                         ans=max({ans,a[i]+x1+y1,a[i]+x2+y2});
  403.                     }
  404.                     else{
  405.                         ans=max(ans,a[i]+x+y);
  406.                     }
  407.                 }
  408.             }
  409.         }
  410.         cout<<ans<<'\n';
  411.     }
  412. }
Runtime error #stdin #stdout 0.04s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/NugESH
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!