fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. const int N=20005;
  10. const int INF=-1;
  11. int n,m,p;
  12. int a[N];
  13. int b[N];
  14. int F[2][N];
  15. int Ra[N];
  16. int Rb[N];
  17. string Path;
  18.  
  19. inline
  20. void checkmax(int &t,const int x){
  21.     if (x>t) t=x;
  22. }
  23.  
  24. inline int w(int i,int j){
  25.     int ret=a[i]+b[j];
  26.     if (ret>=p) ret-=p;
  27.     return ret;
  28. }
  29.  
  30. long long Gao(int sx,int sy,int ex,int ey){
  31.     if (sx==ex && sy==ey) return w(sx,sy);
  32.     int step=ex-sx + ey-sy;
  33.     if (step==1){
  34.        if (sx<ex) Path+='C';
  35.              else Path+='S';
  36.        return w(sx,sy)+w(ex,ey);
  37.     }
  38.     int s1=step/2;
  39.     int s2=step-s1;
  40.     for (int j=0;j+sy<=ey;j++) F[0][j]=F[1][j]=INF;
  41.     for (int j=sy;j<=ey;j++) Ra[j]=Rb[j]=INF;
  42.     F[0][0]=w(sx,sy);
  43.     for (int i=1;i<=s1;i++){
  44.         int p=i&1;
  45.         for (int j=max(0,i+sx-ex);j<=i && j<=ey-sy;j++){
  46.             F[p][j]=INF;
  47.             int nx=i-j+sx;
  48.             int ny=sy+j;
  49.             if (F[p^1][j]!=INF)
  50.             checkmax(F[p][j],F[p^1][j]+w(nx,ny));
  51.             if (j && F[p^1][j-1]!=INF)
  52.             checkmax(F[p][j],F[p^1][j-1]+w(nx,ny));
  53.             if (i==s1) Ra[ny]=F[p][j];
  54.         }
  55.     }
  56.  
  57.     for (int j=0;j+sy<=ey;j++) F[0][j]=F[1][j]=INF;
  58.     F[0][0]=w(ex,ey);
  59.     for (int i=1;i<=s2;i++){
  60.         int p=i&1;
  61.         for (int j=max(0,sx+i-ex);j<=i && j<=ey-sy;j++){
  62.             F[p][j]=INF;
  63.             int nx=ex-(i-j);
  64.             int ny=ey-j;
  65.             if (F[p^1][j]!=INF)
  66.             checkmax(F[p][j],F[p^1][j]+w(nx,ny));
  67.             if (j && F[p^1][j-1]!=INF)
  68.             checkmax(F[p][j],F[p^1][j-1]+w(nx,ny));
  69.             if (i==s2) Rb[ny]=F[p][j]-w(nx,ny);
  70.         }
  71.     }
  72.     int bx=-1;
  73.     int by=-1;
  74.     int ret=-1;
  75.     for (int j=sy;j<=ey;j++){
  76.         if (Ra[j]!=INF && Rb[j]!=INF && Ra[j]+Rb[j]>ret){
  77.           bx=sx+s1-(j-sy);
  78.           by=j;
  79.           ret=Ra[j]+Rb[j];
  80.         }
  81.     }
  82.     Gao(sx,sy,bx,by);
  83.     Gao(bx,by,ex,ey);
  84.     return ret;
  85. }
  86.  
  87. int main(){
  88.     scanf("%d%d%d",&n,&m,&p);
  89.     for (int i=0;i<n;i++) { scanf("%d",&a[i]); a[i]%=p; }
  90.     for (int i=0;i<m;i++) { scanf("%d",&b[i]); b[i]%=p; }
  91.     cout << Gao(0,0,n-1,m-1) << endl;
  92.     cout << Path << endl;
  93. }
  94.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/XgoR1
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

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!